Fine-grained complexity

В курсе будет рассказано о современном направлении в теории сложности - fine-grained complexity. В рамках этого направления ресурсы, необходимые для выполнения задачи (например, время работы алгоритма), изучаются с более высокой точностью, чем это делается в классической сложности. Например, в рамках классического подхода, если задача разрешима за полиномиальное время, то её считают простой. Однако на практике есть грандиозная разница между простой задачей, которая считается за n2n2, и простой задачей, которая считается за n100n100.

Fine grained complexity пытается ответить на вопрос - какой ассимптотически лучший алгоритм существует для конкретной задачи. Таким образом, с одной стороны, это область вбирает в себя алгоритмы, а с другой — разноообразные методы доказательств нижних оценок.