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

В теории сложности вычислений гипотеза экспоненциального времени — это недоказанное предположение о вычислительной сложности , сформулированное Импальяццо и Патури (1999) . В нем говорится, что выполнимость булевых формул 3-КНФ не может быть решена за субэкспоненциальное время . $2^{o(n)}$. Точнее, обычная форма гипотезы утверждает существование числа $s_{3}>0$ такая, что все алгоритмы, корректно решающие эту задачу, требуют времени как минимум $2^{s_{3}n}.$ Гипотеза экспоненциального времени, если она верна, будет означать, что P ≠ NP , но это более сильное утверждение. Это означает, что многие вычислительные задачи эквивалентны по сложности в том смысле, что если одна из них имеет алгоритм субэкспоненциального времени, то они все имеют его, и что многие известные алгоритмы для этих задач имеют оптимальную или почти оптимальную временную сложность.

Определение

The $k$-SAT- проблема — это версия булевой проблемы выполнимости , в которой входными данными для задачи является логическое выражение в конъюнктивной нормальной форме (т. е. множество и переменных их отрицаний) с не более чем $k$ переменные для каждого предложения. Цель состоит в том, чтобы определить, можно ли сделать это выражение истинным путем присвоения логических значений его переменным. 2-SAT имеет алгоритм с линейным временем , но все известные алгоритмы для большего $k$ возьмем экспоненциальное время , при этом основание показательной функции зависит от $k$. Например, вероятностный алгоритм WalkSAT может решить $k$-СБ в среднее время $$\left(2-{\frac {2}{k}}\right)^{n}n^{O(1)},$$ где $n$ количество переменных в заданном $k$-САТ экземпляр. Для каждого целого числа $k\geq 3$, определять $s_{k}$ быть наименьшим числом таким, что $k$-SAT можно решить вовремя $2^{s_{k}n+o(n)}$. Этот минимум может не существовать, если последовательность все лучших и лучших алгоритмов будет иметь соответственно меньший экспоненциальный рост в своих временных границах; в таком случае определите $s_{k}$ быть нижней границей действительных чисел $\delta$ для чего $k$-SAT можно решить вовремя $O(2^{\delta n})$. Поскольку проблемы с более крупными $k$ не может быть проще, эти числа упорядочены как $s_{3}\leq s_{4}\leq \cdots$, а из-за WalkSAT они максимум $$s_{k}\leq \log _{2}\left(2-{\frac {2}{k}}\right)<1.$$ Гипотеза экспоненциального времени — это гипотеза о том, что все они отличны от нуля или, что то же самое, что наименьшее из них $s_{3}$, не равно нулю.

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

Потому что цифры $s_{3},s_{4},\dots$ образуют монотонную последовательность , ограниченную сверху единицей, они должны сходиться к пределу $$s_{\infty }=\lim _{k\to \infty }s_{k}.$$ Сильная гипотеза экспоненциального времени (SETH) – это гипотеза о том, что $s_{\infty }=1$.

Подразумеваемое

Удовлетворенность

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

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

Предельное значение $s_{\infty }$ последовательности чисел $s_{k}$ самое большее равно $s_{\operatorname {CNF} }$, где $s_{\operatorname {CNF} }$ это нижняя часть чисел $\delta$ такие, что выполнимость формул конъюнктивной нормальной формы без ограничений на длину предложений может быть решена за время $O(2^{\delta n})$. Следовательно, если гипотеза сильного экспоненциального времени верна, то не будет алгоритма общей выполнимости КНФ, который был бы значительно быстрее, чем перебор методом грубой силы по всем возможным присвоениям истины . Однако даже если гипотеза сильной экспоненциальной зависимости времени не сработает, все равно будет возможно $s_{\operatorname {CNF} }$ равняться одному.

Другие проблемы с поиском

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

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

Гипотеза экспоненциального времени также подразумевает, что задача множества дуг взвешенной обратной связи на турнирах не имеет параметризованного алгоритма с временем выполнения. ${\textstyle O(2^{o({\sqrt {\operatorname {OPT} }})}n^{O(1)})}$. Однако у него есть параметризованный алгоритм с временем выполнения. ${\textstyle O(2^{O({\sqrt {\operatorname {OPT} }})}n^{O(1)})}$.

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

Сложность связи

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

Структурная сложность

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

В параметризованной теории сложности, поскольку гипотеза экспоненциального времени подразумевает, что не существует управляемого алгоритма с фиксированным параметром для максимальной клики, это также означает, что W[1] ≠ FPT . В этой области остается важной открытой проблемой, можно ли обратить это импликацию вспять: подразумевает ли W[1] ≠ FPT гипотезу экспоненциального времени? Существует иерархия параметризованных классов сложности, называемая М-иерархией, которая чередует W-иерархию в том смысле, что для всех $i$, ${\mathsf {M}}[i]\subseteq {\mathsf {W}}[i]\subseteq {\mathsf {M}}[i+1]$; например, задача нахождения вершинного покрытия размера $k\log n$ в $n$-граф вершин с параметром $k$ является полным для M[1]. Гипотеза экспоненциального времени эквивалентна утверждению, что M[1] ≠ FPT , и вопросу о том, является ли ${\mathsf {M}}[i]\subseteq {\mathsf {W}}[i]$ для $i>1$ также открыт.

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

См. также

• Теорема Савича , показывающая, что аналогичный экспоненциальный разрыв не может иметь место для пространственной сложности.

Дальнейшее чтение

• Данцин, Евгений; Вулперт, Александр (2010), «Об умеренно экспоненциальном времени для SAT», Теория и применение тестирования выполнимости – SAT 2010 , Конспекты лекций по информатике, том. 6175, Springer-Verlag, стр. 313–325, номер документа : 10.1007/978-3-642-14186-7_27 , ISBN.  978-3-642-14185-0