Рассмотрим следующие алгоритмические задачи:

• Расстояние редактирования: даны две строки длины \(n\), найти их редакционное расстояние.
• 3-сумма: даны \(n\) целых чисел, проверить, дают ли какие три из них в сумме ноль.
• Ортогональные векторы: даны \(n\) векторов, проверить, ортогональны ли какие-то два из них.
• Все пары кратчайших путей: дан взвешенный граф с \(n\) вершинами, найти попарные кратчайшие расстояния.
• Отрицательный треугольник: дан взвешенный граф с \(n\) вершинами, проверить, есть ли в нём треугольник отрицательного веса.
• Выполнимость: дана формула с \(n\) переменными в конъюнктивной нормальной форме, проверить, выполнима ли она.
• Клика: дан граф с \(n\) вершинами и число \(k\), проверить, есть ли в графе клика размера \(k\) (то есть \(k\) вершин, попарно соединённых рёбрами).

Хорошо известно, что некоторые из этих задач принадлежат классу P, то есть могут быть решены за полиномиальное время, а некоторые — NP-полны, что означает, что никто для этих задач не знает полиномиального алгоритма (если найти такой алгоритм для хотя бы одной NP-полной задачи, то сразу все задачи из класса NP решатся за полиномиальное время и вообще окажется, что P=NP). Но разделение на классы P и NP слишком грубое: оно ничего не говорит про то, можно ли, например, задачу о редакционном расстоянии решить за время \(n^{1.99}\) или задачу выполнимости — за время \(1.99^n\). Существование обоих упомянутых только что алгоритмов — большая открытая задача. Построить такие алгоритмы было бы интересно как с теоретической, так и с практической точек зрения.

Область под названием fine grained complexity, активно развивающаяся в последнее десятилетие, пытается дать ответы на эти вопросы. На многие интересные вопросы ответов у нас так и нет, но зато были найдены некоторые удивительные связи. Например, доказано, что если есть алгоритм для задачи о редакционном расстоянии со временем работы \(n^{1.9}\), то есть и алгоритм для задачи выполнимости со временем работы \(1.999^n\). Доказано также, что задачу о кратчайших путях можно решить за время \(\frac{n^3}{2^{\sqrt{\log n}}}\).

В курсе мы познакомимся с современным положением дел в этой области: узнаем и последние результаты, и открытые задачи. После каждой лекции будет выдаваться домашнее задание. Оценка за курс будет ставиться по результатам решения этих домашних заданий. Курс будет читаться по материалам курса, прочитанного летом 2019 г. Карлом Брингманом и Марвином Кунеманом: https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/summer19/fine-complexity/