Fine-grained complexity

Мы уже привыкли к тому, что выражение «задача NP-трудна» стало синонимом «задача не решается за полиномиальное время», хотя неравенство классов P и NP до сих пор не доказано. А что, если задача всё-таки решается за полиномиальное время, но сам порядок полинома нас не очень устраивает? Например,

– Можем ли мы быстрее $n^2$ найти среди набора из $n$ бинарных строк две строки, у которых не совпадает ни один единичный бит?

– Можно ли найти в заданном наборе три числа с заданной суммой существенно быстрее $n^2$?

– Вычислим ли радиус заданного графа быстрее $n^3$?

В курсе мы постараемся установить связи между этими и другими классическими алгоритмическими задачами, многие из которых широко применяются и не являются NP-трудными. Например, докажем, что алгоритм со временем работы $n^{1.9}$ для первой задачи позволит решать задачу выполнимости быстрее $1.9999^n$; а третий вопрос неразрывно связан с кубическим алгоритмом для задачи APSP вычисления матрицы кратчайших расстояний.

В отличие от полиномиальных сведений, которые используются для доказательства NP-трудности, в fine-grained сведениях мы будем более детально следить за временем работы и размером задачи (отсюда и название). Например, мы покажем, что задача из первого вопроса сводится (за время быстрее, чем $n^{1.9}$) к поиску наибольшей общей подпоследовательности (Longest Common Subsequence, LCS) заданных двух строк длины $\mathcal{O}(n)$. Как следствие, алгоритм со временем работы $n^{1.9}$ для LCS повлечёт $1.9999^n$-алгоритм для задачи выполнимости.

Мы познакомимся с известными результаты области, как с классическими, так и с более современными, рассмотрим открытые вопросы, поговорим о лучших известных алгоритмах для некоторых из задач и о препятствиях для сведения их друг к другу.

Пререквизиты: для восприятия курса потребуется знакомство с базовым курсом алгоритмов.