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

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

В последние годы эта область породила много очень интересных результатов, включая:

• несколько алгоритмов, которые исследователи пытались улучшить около полувека на самом деле оказались оптимальными. Этот список включает алгоритмы для задачи поиска наибольшей общей подпоследовательности и задачи нахождения редакционного расстояния.
• для классических задач, таких как поиск всех кратчайших расстояний в графе или нахождения пары ортогональных векторов были найдены более быстрые алгоритмы.