Гипотеза об экспоненциальном времени

Гипотеза об экспоненциальном времени — это недоказанное допущение о вычислительной сложности, которое сформулировали Импальяццо и Патури. Гипотеза утверждает, что 3-SAT (или любая из связанных NP-полных задач) не может быть решена за субэкспоненциальное время в худшем случае. Из верности гипотезы об экспоненциальном времени, если она верна, следовало бы, что P ≠ NP, но гипотеза является более сильным утверждением. Из утверждения гипотезы можно показать, что многие вычислительные задачи эквиваленты по сложности в том смысле, что если одна из них имеет алгоритм экспоненциального времени, то все они имеют алгоритмы такой же сложности.

Определение

Задача k-SAT является задачей проверки, можно ли логическое выражение в конъюнктивной нормальной форме, имеющее более k переменных на (конъюнктивное) выражение, сделать верным путём присвоения значения булевских значений переменным выражения. Для любого целого $k\geqslant 2$ определим вещественное число $s_{k}$ как инфимумом вещественных чисел $\delta$, для которых существует алгоритм решения задачи k-SAT за время $O(2^{\delta n})$, где n — число переменных в данной задаче k-SAT. Тогда $s_{2}=0$, поскольку задача 2-SAT может быть решена за полиномиальное время. Гипотеза об экспоненциальном времени — это предположение, что для любого $k>2,s_{k}>0$. Ясно, что $s_{3}\leqslant s_{4}\leqslant \ldots$, так что гипотеза эквивалентна предположению, что $s_{3}>0$, положительность оставшихся чисел $s_{k}$ следует автоматически из предположения.

Некоторые источники определяют гипотезу об экспоненциальном времени в виде несколько более слабого утверждения, что 3-SAT не может быть решена за время $2^{o(n)}$. Если существует алгоритм решения задачи 3-SAT за время $2^{o(n)}$, то ясно, что $s_{3}$ будет равно нулю. Однако это согласуется с текущим знанием, что может существовать последовательность 3-SAT алгоритмов, каждый из которых работает за время $O(2^{\delta _{i}n})$ для чисел $\delta _{i}$, стремящихся к нулю, но описание этих алгоритмов быстро растёт, так что один алгоритм не в состоянии автоматически выбрать и выполнить наиболее подходящий алгоритм.

Поскольку числа $s_{3},s_{4},\ldots$ образуют монотонную последовательность, которая сверху ограничена единицей, они должны сходиться к пределу $s_{\infty }$. Сильная гипотеза об экспоненциальном времени (SETH) — это предположение, что предельное значение s_∞ последовательности чисел s_k равно единице.

Другой вариант гипотезы — неоднородная гипотеза об экспоненциальном времени, усиливающая вторую часть ETH, которая постулирует, что не существует семейства алгоритмов (по одному на каждую длину входа в духе подсказки), которое может решить задачу 3-SAT за время 2^o(n).

Следствие для выполнимости

Не может $s_{k}$ быть равным $s_{\infty }$ для любого конечного k — как показали Импальяццо, Патури и Зейн, существует константа $\alpha$, такая что $s_{k}\leqslant s_{\infty }(1-\alpha /k)$. Поэтому, если гипотеза об экспоненциальном времени верна, должно быть бесконечно много значений k для которых s_kотличается от $s_{k+1}$.

Важное средство в этой области — лемма о разрежении Импальяццо, Патури и Зейна, которая показывает, что для любого $\epsilon >0$ любая k-CNF формула может быть заменена $O(2^{{\epsilon }n})$ более простыми k-CNF формулами, в которых каждая переменная появляется лишь постоянное число раз, а потому число предложений линейно. Лемма о разрежении доказана путём последовательного нахождения больших множеств выражений, имеющих непустое общее пересечение в заданной формуле, и заменой формулы двумя более простыми формулами, в одной из которых каждое такое выражение заменяется их общим пересечением, а в другой пересечении удаляется из каждого выражения. При применении леммы разрежения и использовании новых переменных для расщепления выражений можно получить множество из $O(2^{\epsilon }n)$ 3-CNF формул, каждое с линейным числом переменных, так что исходная k-CNF формула является выполнимой тогда и только тогда, когда по меньшей мере одна из этих 3-CNF формул выполнима. Таким образом, если 3-SAT могла бы быть решена за субэкспоненциальное время, можно использовать это приведение для решения задачи k-SAT за субэкспоненциальное время. Эквивалентно, если $s_{k}>0$ для любого k > 3, то $s_{3}>0$ и гипотеза об экспоненциальном времени верна.

Предельное значение $s_{\infty }$ последовательности чисел s_k не превосходит s_CNF, где s_CNF — инфимум чисел $\delta$, таких что выполнимость формул в конъюнктивной нормальной форме без ограничения длины выражения может быть решена за время $O(2:{{\delta }n})$. Таким образом, если сильная гипотеза об экспоненциальном времени верна, то не существует алгоритма для общей задачи CNF выполнимости, который существенно быстрее, чем проверка всех возможных высказываний на истинность. Однако если сильная гипотеза об экспоненциальном времени не верна, для s_CNF остаётся возможность равенства единице.

Следствия для задач поиска

Из гипотезы об экспоненциальном времени вытекает, что многие другие задачи в классе сложности SNP не имеют алгоритмов, время работы которых меньше чем cⁿ для некоторой константы  c. В эти задачи входят k-раскрашиваемость графа, нахождение гамильтоновых циклов, наибольших клик, наибольших независимых множеств и вершинных покрытий на графах с n вершинами. Обратно, если любая из этих задач имеет субэкспоненциальный алгоритм, то можно будет показать, что гипотеза об экспоненциальном времени неверна.

Если клики или независимые множества логарифмического размера можно было бы найти за полиномиальное время, гипотеза об экспоненциальном времени была бы неверна. Таким образом, даже если нахождение клик или независимых множеств такого малого размера вряд ли являются NP-полными задачами, из гипотезы об экспоненциальном времени вытекает, что эти задачи не полиномиальны. Более обще из гипотезы об экспоненциальном времени следует, что невозможно найти клики или независимые множества размером k за время $n^{o(k)}$. Из гипотезы об экспоненциальном времени также вытекает, что невозможно решить задачу k-SUM (даны n вещественных чисел, нужно найти k из них, дающих сумме нуль) за время $n^{o(k)}$. Из сильной гипотезы об экспоненциальном времени следует, что невозможно найти доминирующие множества, состоящие из k вершин быстрее, чем за время $n^{k-o(1)}$.

Из гипотезы об экспоненциальном времени следует также, что взвешенная задача нахождения разрезающего циклы набора дуг на турнирах (FAST) не имеет параметрического алгоритма со временем работы $O^{*}(2^{o({\sqrt {OPT}})})$, она даже не имеет параметрического алгоритма со временем работы $O^{*}(2^{O({\sqrt {OPT}})})$.

Сильная гипотеза об экспоненциальном времени приводит к точным границам параметризованной сложности некоторых задач на графах с ограниченной древесной шириной. В частности, если сильная гипотеза об экспоненциальном времени верна, то граница оптимального времени поиска независимых множеств на графах с древесной шириной w равна $(2o(1))^{w}n^{O(1)}$, оптимальное время для задачи о доминирующем множестве равно $(3-o(1))^{w}n^{O(1)}$, оптимальное время для максимального разреза графа равно $(2-o(1))^{w}n^{O(1)}$, а оптимальное время для k-раскраски равно $(k-o(1))^{w}n^{O(1)}$. Эквивалентно, любое улучшение этих времён работы приводит к неверности сильной гипотезы об экспоненциальном времени. Из гипотезы об экспоненциальном времени также следует, что любой фиксированно-параметрически разрешимый алгоритм для покрытия рёбер графа кликами должен иметь двойную экспоненциальную зависимость от параметра.

Следствия в теории сложности коммуникации

В задаче трёхсторонней дизъюнктности множеств в коммуникационной сложности задаются три подмножества целых чисел из некоторого интервала [1,m] и даны три общающихся участника, каждый из которых знает два из трёх подмножеств. Целью участников является передать как можно меньше битов информации друг другу по общему коммуникационному каналу, но чтобы один из участников смог определить, является ли пересечение трёх множеств пустым или не пустым. Тривиальным m-битовым протоколом была бы посылка одного из участников битового вектора, описывающего пересечение двух известных ему множеств, после чего каждый из оставшихся двоих участников может определить пустоту пересечения. Однако, если существует протокол, решающий задачу за o(m) пересылок и $2^{o(m)}$ вычислений, он может быть преобразован в алгоритм решения k-SAT за время O(1,74ⁿ) для любой фиксированной константы k, что нарушает сильную гипотезу об экспоненциальном времени. Поэтому из сильной гипотезы об экспоненциальном времени следует, что либо тривиальный протокол для задачи о трёхсторонней дизъюнктивности множеств является оптимальным, либо любой лучший протокол требует экпоненциального числа вычислений.

Следствия в теории структурной сложности

Если гипотеза об экспоненциальном времени верна, то 3-SAT не должна иметь алгоритма полиномиального времени, а потому из этого следовало бы, что P ≠ NP. Более сильно, в этом случае задача 3-SAT не имела бы даже алгоритма квази-полиномиального времени, так что NP не могло бы быть подмножеством класса QP. Однако, если гипотеза об экспоненциальном времени не верна, из этого не следовало бы равенство классов P и NP. Существуют NP-полные задачи, для которых лучшее известное время решения имеет вид $O(2^{n^{c}})$ для $c<1$, и если бы лучшее возможное время работы для 3-SAT имело такой вид, то P был бы не равен NP (поскольку 3-SAT является NP-полной задачей, а это время не полиномиально), но гипотеза об экспоненциальном времени была бы не верна.

В теории параметрической сложности, поскольку из гипотезы об экспоненциальном времени вытекает, что не существует фиксированно-параметрически разрешимого алгоритма для нахождения наибольшей клики, из её также следует, что W[1] ≠ FPT. Является важной открытой проблемой в этой области, может ли обратить это следствие — следует ли из $W[1]\neq FPT$ гипотеза об экспоненциальном времени? Существует иерархия классов параметрической сложности, называемая M-иерархией, которая перемежается с W-иерархией в том смысле, что для всех i, $M[i]\subseteq W[i]\subseteq M[i+1]$. Например, задача поиска вершинного покрытия размера $k\log(n)$ в графе с n вершинами является полной для M[1]. Гипотеза об экспоненциальном времени эквивалентна утверждению, что $M[1]\neq FPT$, а вопрос о равенстве $M[i]=W[i]$ для i > 1 также остаётся открытым.

Можно также показать вывод в другом направлении, из неверности варианта сильной гипотезы об экспоненциальном времени к разделению классов сложности. Как показал Уильямс, если существует алгоритм A, который решает задачу о выполнимости булевской схемы время $2^{n}/f(n)$ для некоторой суперполиномиально растущей функции $f$, то NEXPTIME не является подмножеством P/poly. Уильямс показал, что если алгоритм A существует и семейство схем, моделирующее NEXPTIME в P/poly также существует, то алгоритм A можно было бы скомбинировать со схемой для моделирования задач NEXPTIME недетминированно за меньшее время, что противоречит теореме о иерархии времени. Таким образом, существование алгоритма A доказывает невозможность существования семейства схем и разделение этих двух классов сложности.