City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Fine-grained Complexity


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

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

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

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

Course Offerings

Semester Branch
autumn 2020 Saint Petersburg