Александр Куликов "Полиномиальные формулировки как препятствие к доказательству условных нижних оценок на вычислительную сложность"
Во вторник 22 апреля в 18:00 по Московскому времени на Большом Семинаре состоится доклад Александра Куликова (JetBrains, биография). Александр будет говорить на тему "Полиномиальные формулировки как препятствие к доказательству условных нижних оценок на вычислительную сложность".
Password: 088551
Аннотация:
Сильная гипотеза экспоненциального времени (Strong Exponential Time Hypothesis, SETH) утверждает, что задачу выполнимости нельзя решить существенно быстрее, чем за время $2^n$. В последние годы в предположении этой гипотезы было доказано много нижних оценок на вычислительную сложность самых разных задач: $n^2$ для задачи о расстоянии редактирования, $2^n$ для задачи о покрывающем множестве, 2^{древесная ширина} для задачи о независимом множестве. Можно предположить, что SETH может служить препятствием и для других вычислительных задач. Мы покажем, что для многих других интересных задач доказать нижнюю оценку в предположении SETH будет сложно: это автоматически дало бы новые нижние оценки на схемную сложность, которые не удаётся доказать уже несколько десятилетий.