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

Недоказанное предположение о вычислительной сложности

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

Определение

Проблема -SAT — это версия проблемы логической выполнимости , в которой входными данными для задачи является логическое выражение в конъюнктивной нормальной форме ( т. е. множество переменных и их отрицаний) с не более чем переменными в каждом предложении. Цель состоит в том, чтобы определить, можно ли сделать это выражение истинным путем присвоения логических значений его переменным. 2-SAT имеет алгоритм с линейным временем , но все известные алгоритмы для большего времени используют экспоненциальное время с основанием экспоненциальной функции, зависящим от . Например, вероятностный алгоритм WalkSAT может решить -SAT в среднем за время. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

$${\displaystyle \left(2-{\frac {2}{k}}\right)^{n}n^{O(1)},}$$

-SAT . ^[2]целого числа определитеможновремя . нижнюю границу-SATвремя . , ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k\geq 3}$ ${\displaystyle s_{k}}$ ${\displaystyle k}$ ${\displaystyle 2^{s_{k}n+o(n)}}$ ${\displaystyle s_{k}}$ ${\displaystyle \delta }$ ${\displaystyle k}$ ${\displaystyle O(2^{\delta n})}$ ${\displaystyle k}$ ${\displaystyle s_{3}\leq s_{4}\leq \cdots }$

$${\displaystyle s_{k}\leq \log _{2}\left(2-{\frac {2}{k}}\right)<1.}$$

экспоненциального временигипотеза о том, что все они ненулевые или, что то же самое ,от нуля. ^[1] ${\displaystyle s_{3}}$

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

Поскольку числа образуют монотонную последовательность , ограниченную сверху единицей, они должны сходиться к пределу ${\displaystyle s_{3},s_{4},\dots }$

$${\displaystyle s_{\infty }=\lim _{k\to \infty }s_{k}.}$$

экспоненциальная гипотеза временио том, что . ^[5] ${\displaystyle s_{\infty }=1}$

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

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

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

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

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

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

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

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

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

Гипотеза сильного экспоненциального времени приводит к жестким ограничениям параметризованной сложности некоторых задач с графами на графах ограниченной ширины дерева . В частности, если гипотеза сильного экспоненциального времени верна, то оптимальное время для поиска независимых множеств на графах ширины дерева ${\displaystyle 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)}}$ а оптимальное время для -окраска есть . ^[12] Аналогично, любое улучшение этого времени выполнения фальсифицирует гипотезу сильной экспоненциальной зависимости времени. ^[13] Гипотеза экспоненциального времени также подразумевает, что любой управляемый алгоритм с фиксированным параметром для покрытия реберной клики должен иметь двойную экспоненциальную зависимость от параметра. ^[14] ${\displaystyle k}$ ${\textstyle {\bigl (}k-o(1){\bigr )}^{w}n^{O(1)}}$

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

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

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

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

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

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

Смотрите также

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

Примечания

1. Импальяццо, Рассел ; Патури, Рамамохан (1999), «Сложность k-SAT», Proc. 14-я конференция IEEE. о сложности вычислений , стр. 237–240, doi : 10.1109/CCC.1999.766282, ISBN. 978-0-7695-0075-1, S2CID  442454
2. Шёнинг, Уве (1999), «Вероятностный алгоритм для -SAT и проблем удовлетворения ограничений», 40-й ежегодный симпозиум по основам информатики, FOCS '99, 17-18 октября 1999 г., Нью-Йорк, Нью-Йорк, США , IEEE Computer Общество, стр. 410–414, номер документа : 10.1109/SFCS.1999.814612, S2CID  1230959. ${\displaystyle k}$
3. Флум, Йорг; Гроэ, Мартин (2006), «16. Субэкспоненциальная управляемость с фиксированными параметрами», Параметризованная теория сложности , Тексты EATCS по теоретической информатике, Springer-Verlag, стр. 417–451, ISBN 978-3-540-29952-3
4. Чен, Ицзя; Эйкмейер, Корд; Флум, Йорг (2012), «Гипотеза экспоненциального времени и проблема параметризованной клики», в Тиликосе, Димитриосе М.; Воегингер, Герхард Дж. (ред.), Параметризованные и точные вычисления - 7-й Международный симпозиум, IPEC 2012, Любляна, Словения, 12–14 сентября 2012 г., Труды , Конспекты лекций по информатике, том. 7535, Springer, стр. 13–24, CiteSeerX 10.1.1.680.8401 , номер документа : 10.1007/978-3-642-33293-7_4. 
5. Калабро, Крис; Импальяццо, Рассел ; Патури, Рамамохан (2009 г.), «Сложность выполнимости схем малой глубины», Параметризованные и точные вычисления, 4-й международный семинар, IWPEC 2009, Копенгаген, Дания, 10–11 сентября 2009 г., Пересмотренные избранные статьи , Конспекты лекций по информатике , том. 5917, стр. 75–85, CiteSeerX 10.1.1.331.764 , номер документа : 10.1007/978-3-642-11269-0_6. 
6. Импальяццо, Рассел ; Патури, Рамамохан; Зейн, Фрэнсис (2001), «Какие проблемы имеют сильно экспоненциальную сложность?», Journal of Computer and System Sciences , 63 (4): 512–530, CiteSeerX 10.1.1.66.3717 , doi :10.1006/jcss.2001.1774 
7. Woeginger, Герхард (2003), «Точные алгоритмы для NP-сложных задач: обзор», Комбинаторная оптимизация — Эврика, ты уменьшаешься! (PDF) , Конспекты лекций по информатике, том. 2570, Springer-Verlag, стр. 185–207, CiteSeerX 10.1.1.168.5383 , doi : 10.1007/3-540-36478-1_17, ISBN  978-3-540-00580-3, S2CID  289357
8. Патрашку, Михай ; Уильямс, Райан (2010), «О возможности более быстрых алгоритмов SAT», Proc. 21-й симпозиум ACM/SIAM по дискретным алгоритмам (SODA 2010) (PDF) , стр. 1065–1075
9. Файги, Уриэль ; Килиан, Джо (1997), «Об ограниченном и полиномиальном недетерминизме», Чикагский журнал теоретической информатики , 1 : 1–20, doi : 10.4086/cjtcs.1997.001
10. Чен, Цзянер; Хуан, Сючжэнь; Кандж, Ияд А.; Ся, Ге (2006), «Сильные вычислительные нижние границы посредством параметризованной сложности», Journal of Computer and System Sciences , 72 (8): 1346–1367, doi : 10.1016/j.jcss.2006.04.007
11. Карпински, Марек ; Шуди, Уоррен (2010), «Быстрые алгоритмы для турнира по набору дуг обратной связи, турнира по агрегированию рангов Кемени и турнира по взаимосвязи», Proc. ISAAC 2010, Часть I , Конспекты лекций по информатике, 6506 : 3–14, arXiv : 1006.4396 , doi : 10.1007/978-3-642-17517-6_3, ISBN 978-3-642-17516-9, S2CID  16512997
12. Сиган, Марек; Фомин Федор Владимирович; Ковалик, Лукаш; Локштанов Даниил; Маркс, Дэниел; Пилипчук, Марцин; Пилипчук, Михал; Саураб, Сакет (2015), Параметризованные алгоритмы , Springer, стр. 555, ISBN 978-3-319-21274-6
13. Локштанов, Даниил; Маркс, Даниэль; Саураб, Сакет (2011), «Известные алгоритмы на графах ограниченной ширины дерева, вероятно, оптимальны», Proc. 22-й симпозиум ACM/SIAM по дискретным алгоритмам (SODA 2011) , стр. 777–789, arXiv : 1007.5450 , doi : 10.1137/1.9781611973082.61, S2CID  1810488
14. Сиган, Марек; Пилипчук, Марцин; Пилипчук, Михал (2016), «Известные алгоритмы покрытия реберной клики, вероятно, оптимальны», SIAM Journal on Computing , 45 (1): 67–83, arXiv : 1203.1754 , doi : 10.1137/130947076, MR  3448348, S2CID  11264145
15. Уильямс, Райан (2010), «Улучшение исчерпывающего поиска подразумевает суперполиномиальные нижние границы», Proc. 42-й симпозиум ACM по теории вычислений (STOC 2010) , Нью-Йорк, штат Нью-Йорк, США: ACM, стр. 231–240, CiteSeerX 10.1.1.216.1299 , doi : 10.1145/1806689.1806723, ISBN  9781450300506, S2CID  651703

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

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