Полиномиальные формулировки как барьер для доказательств сложности

Теория сложности пытается ответить на вопросы о минимальном количестве ресурсов необходимых на решение алгоритмической задачи. В классическом варианте ответ на такой вопрос представляется в виде отнесение задачи к какому-то сложностному классу, например к классу P — задачам решаемым за полиномиальное время. При этом решается задача за $n^2$ или за $n^{100}$ уже неважно. В последние годы активно развивается другой подход известный как теория высокоточных оценок, где сложность решение задач пытаются измерить наоборот максимально точно. Поскольку у нас пока нет примеров безусловных оценок на сложность задач, эта теория оперерует нижними оценками в предположении различных гипотез. В этом докладе мы поговорим о том как такие оценки доказываются в предположении Strong exponential time hypothesis и почему для каких-то задач такие нижние оценки будут иметь невероятно сильные последствия для других областей теории сложности. Доклад будет состоять из обзорной части и краткого разговора о нашей последней статье “Polynomial formulations as a barrier for reduction-based hardness proofs”.