💡 Fine-grained complexity
– Страница курса
– Первая лекция 22 марта, 12:00. Расписание лекций можно найти на сайте
– Мраморный зал, ПОМИ РАН, наб. реки Фонтанки, 27, Санкт-Петербург
– Пожалуйста, не забудьте зарегистрироваться — это необходимое условие посещения ПОМИ РАН. Достаточно сделать это один раз для посещения любой лекции курса.
⭐️ О лекторе
Данил Сагунов
– Научный сотрудник ИТМО, МКН СПбГУ; выпускник магистратуры Академического Университета РАН по направлению Теоретическая информатика
– Научные интересы: parameterized complexity, algorithmic graph theory, exact algorithms, algorithms for NP-hard problems, kernelization, computational complexity, graph algorithms and parameters
– Финалист ICPC 2016
– Координатор Сodeforces и HackerRank 2016
– Личная страница: danilka.pro
📢 Анонс
Мы уже привыкли к тому, что выражение «задача 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) заданных двух строк длины O(n). Как следствие, алгоритм со временем работы n^1.9 для LCS повлечёт 1.9999^n-алгоритм для задачи выполнимости.
Мы познакомимся с известными результаты области, как с классическими, так и с более современными, рассмотрим открытые вопросы, поговорим о лучших известных алгоритмах для некоторых из задач и о препятствиях для сведения их друг к другу.
Пререквизиты: для восприятия курса потребуется знакомство с базовым курсом алгоритмов.