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

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

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

Определение

Задача -SAT является версией задачи выполнимости булевых уравнений , в которой входными данными для задачи является булево выражение в конъюнктивной нормальной форме (то есть, and или or переменных и их отрицаний) с не более чем переменными на предложение. Цель состоит в том, чтобы определить, можно ли сделать это выражение истинным путем некоторого присвоения его переменным булевых значений. 2-SAT имеет линейный алгоритм времени, но все известные алгоритмы для больших значений требуют экспоненциальное время , с основанием экспоненциальной функции, зависящим от . Например, вероятностный алгоритм WalkSAT может решить -SAT за среднее время , где - количество переменных в данном экземпляре -SAT . ^[2] Для каждого целого числа определите как наименьшее число, такое, что -SAT может быть решена за время . Этот минимум может не существовать, если последовательность все лучших и лучших алгоритмов имеет соответственно меньший экспоненциальный рост в своих временных границах; в этом случае определите как инфимум действительных чисел , для которых -SAT может быть решена за время . Поскольку проблемы с большими числами не могут быть проще, эти числа упорядочены как , и благодаря WalkSAT они не превышают Гипотеза экспоненциального времени — это предположение о том, что все они не равны нулю, или, что то же самое, что наименьшее из них, , не равно нулю. ^[1] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ $${\displaystyle \left(2-{\frac {2}{k}}\right)^{n}n^{O(1)},}$$ ${\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.}$$ ${\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)}}$

Поскольку числа образуют монотонную последовательность , ограниченную сверху единицей, они должны сходиться к пределу. Сильная экспоненциальная гипотеза времени (SETH) — это предположение о том, что . ^[5] ${\displaystyle s_{3},s_{4},\dots }$ $${\displaystyle s_{\infty }=\lim _{k\to \infty }s_{k}.}$$ ${\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-CNF-формул выполнима. Следовательно, если 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», Труды 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 Society, стр. 410–414, doi :10.1109/SFFCS.1999.814612, S2CID  1230959 ${\displaystyle k}$
3. Flum, Jörg; Grohe, Martin (2006), "16. Субэкспоненциальная трактуемость с фиксированными параметрами", Параметризованная теория сложности , EATCS Texts in Theoretical Computer Science, 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 , doi :10.1007/978-3-642-11269-0_6 
6. Импальяццо, Рассел ; Патури, Рамамохан; Зейн, Фрэнсис (2001), «Какие проблемы имеют строго экспоненциальную сложность?», Журнал компьютерных и системных наук , 63 (4): 512–530, CiteSeerX 10.1.1.66.3717 , doi :10.1006/jcss.2001.1774 
7. Woeginger, Gerhard (2003), "Точные алгоритмы для NP-трудных задач: обзор", Комбинаторная оптимизация — Эврика, вы уменьшаетесь! (PDF) , Lecture Notes in Computer Science, т. 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, заархивировано из оригинала (PDF) 2020-09-30 , извлечено 2011-03-31
8. Pătraşcu, Mihai ; Williams, Ryan (2010), «О возможности более быстрых алгоритмов SAT», Proc. 21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010) (PDF) , стр. 1065–1075
9. Фейге, Уриэль ; Килиан, Джо (1997), «О ограниченном и полиномиальном недетерминизме», Чикагский журнал теоретической компьютерной науки , 1 : 1–20, doi : 10.4086/cjtcs.1997.001
10. Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Сильные нижние вычислительные границы с помощью параметризованной сложности", Журнал компьютерных и системных наук , 72 (8): 1346–1367, doi : 10.1016/j.jcss.2006.04.007
11. Карпински, Марек ; Шуди, Уоррен (2010), «Более быстрые алгоритмы для турнира по набору дуг обратной связи, агрегации рангов Кемени и турнира по промежуточности», Proc. ISAAC 2010, Часть I , Lecture Notes in Computer Science, 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), «Известные алгоритмы на графах ограниченной древовидной ширины, вероятно, оптимальны», Труды 22-го симпозиума ACM/SIAM по дискретным алгоритмам (SODA 2011) , стр. 777–789, arXiv : 1007.5450 , doi : 10.1137/1.9781611973082.61, S2CID  1810488
14. Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał (2016), «Известные алгоритмы для покрытия кликами ребер, вероятно, оптимальны», SIAM Journal on Computing , 45 (1): 67–83, arXiv : 1203.1754 , doi : 10.1137/130947076, MR  3448348, S2CID  11264145
15. Уильямс, Райан (2010), «Улучшение исчерпывающего поиска подразумевает суперполиномиальные нижние границы», Proc. 42nd ACM Symposium on Theory of Computing (STOC 2010) , Нью-Йорк, США: ACM, стр. 231–240, CiteSeerX 10.1.1.216.1299 , doi :10.1145/1806689.1806723, ISBN  9781450300506, S2CID  651703

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

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