Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В теории вычислительной сложности гипотеза экспоненциального времени - это недоказанное предположение о вычислительной сложности , которое было сформулировано Impagliazzo & Paturi (1999) . Гипотеза утверждает, что 3-SAT (или любая из нескольких, но не всех [1] NP-полных задач) не может быть решена за субэкспоненциальное время в худшем случае . [2] Гипотеза экспоненциального времени, если она верна, означала бы, что P ≠ NP, но это более сильное утверждение. Его можно использовать, чтобы показать, что многие вычислительные задачи эквивалентны по сложности в том смысле, что если одна из них имеет алгоритм субэкспоненциального времени, то они все имеют.

Определение [ править ]

k -SAT - это проблема проверки того, может ли логическое выражение в конъюнктивной нормальной форме с не более чем k переменными на предложение быть истинным путем присвоения его переменным логических значений. Для каждого целого числа k ≥ 2 определите действительное число s k какнижнюю грань действительных чисел δ, для которых k -SAT может быть решена алгоритмически за время O (2 δ n ), где n - количество переменных в данном k -SAT экземпляр. Тогда s 2  = 0, потому что 2-SAT может быть решена вполиномиальное время . Причем s 3  ≤  s 4  ≤ ..., так как сложность не уменьшается с ростом k .

Гипотеза экспоненциального времени - это гипотеза о том, что s k  > 0 для любого k  > 2, или, что то же самое, что s 3  > 0.

Некоторые источники определяют гипотезу экспоненциального времени как немного более слабое утверждение, что 3-SAT не может быть решена за время 2 o ( n ) . Если бы существовал алгоритм для решения 3-SAT за время 2 o ( n ) , то s 3 равнялось бы нулю. Однако это согласуется с текущими знаниями о том, что может существовать последовательность алгоритмов 3-SAT, каждый со временем работы O (2 δ i n ) для последовательности чисел δ i, стремящейся к нулю, но где описания этих алгоритмов настолько быстро растёт, что ни один алгоритм не может автоматически выбрать и запустить наиболее подходящий. [3]

Поскольку числа s 3 , s 4 , ... образуют монотонную последовательность , ограниченную сверху единицей, они должны сходиться к пределу s ∞ . Сильная экспоненциальная гипотеза времени (СЕТ) является гипотезой , что ево ∞ = 1. [4]

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

Последствия для выполнимости [ править ]

Невозможно, чтобы s k равнялось s ∞ для любого конечного k : как показали Impagliazzo, Paturi & Zane (2001) , существует константа α такая, что s k  ≤  s ∞ (1 -  α / k ). Следовательно, если гипотеза экспоненциального времени верна, должно быть бесконечно много значений k, для которых s k отличается от s k  + 1 .

Важным инструментом в этой области является лемма о разрежении Impagliazzo, Paturi & Zane (2001) , которая показывает, что для любого ε  > 0 любую формулу k -CNF можно заменить на O (2 εn ) проще k-CNF формулы, в которых каждая переменная встречается только постоянное количество раз, и, следовательно, в которых количество пунктов линейно. Лемма о разрежении доказывается путем многократного нахождения больших наборов предложений, которые имеют непустое общее пересечение в данной формуле, и замены формулы двумя более простыми формулами, в одной из которых каждое из этих предложений заменено их общим пересечением, а в другой перекресток удален из каждого предложения. Применяя лемму о разрежении и затем используя новые переменные для разделения клозов, можно затем получить набор формул O (2 εn ) 3-CNF, каждая с линейным числом переменных, так что исходное kФормула -CNF выполнима тогда и только тогда, когда выполнима хотя бы одна из этих формул 3-CNF. Следовательно, если 3-SAT можно было решить за субэкспоненциальное время, можно было бы использовать это сокращение для решения k -SAT также за субэкспоненциальное время. Эквивалентно, если s k  > 0 для любого k  > 3, то s 3  > также 0, и гипотеза экспоненциального времени будет верной. [2] [5]

Предельное значение s ∞ последовательности чисел s k не больше, чем s CNF , где s CNF - это нижняя грань чисел δ, такая, что выполнимость формул конъюнктивных нормальных формул без ограничения длины предложения может быть решена за время O (2 δn ). Следовательно, если сильная гипотеза экспоненциального времени верна, то не было бы алгоритма для общей выполнимости CNF, который был бы значительно быстрее, чем проверка всех возможных назначений истинности . Однако, если сильная гипотеза экспоненциального времени не сработает, s CNF все равно будет равняться единице. [6]

Последствия для других проблем поиска [ править ]

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

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

Гипотеза экспоненциального времени также подразумевает, что задача взвешенного турнира по набору дуги обратной связи (FAST) не имеет параметризованного алгоритма со временем работы O * (2 o ( √ OPT ) ), но имеет параметризованный алгоритм со временем работы O * ( 2 O ( √ OPT ) ). [9]

Сильная гипотеза экспоненциального времени приводит к жестким ограничениям на параметризованную сложность нескольких задач с графами на графах с ограниченной шириной дерева . В частности, если сильная гипотеза экспоненциального времени верна, то оптимальная оценка времени для нахождения независимых множеств на графах ширины дерева w равна (2 - o (1)) w n O (1) , оптимальное время для задачи доминирующего множества составляет (3 - o (1)) w n O (1) , оптимальное время для максимального разреза составляет (2 - o (1)) w nO (1) , а оптимальное время дляk-раскраски равно( k - o (1)) w n O (1) . [10] Точно так же любое улучшение этого времени работы опровергло бы сильную гипотезу экспоненциального времени. [11] Гипотеза экспоненциального времени также подразумевает, что любой управляемый алгоритм с фиксированными параметрами дляпокрытия краевых кликдолжен иметьдвойную экспоненциальнуюзависимость от параметра. [12]

Влияние на сложность общения [ править ]

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

Последствия структурной сложности [ править ]

Если гипотеза экспоненциального времени верна, то 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 . [8] Это важная открытая проблема в этой области, можно ли обратить эту импликацию вспять: подразумевает ли W [1] ≠ FPT гипотезу экспоненциального времени? Существует иерархия параметризованных классов сложности , называемой М-иерархия, перемежает W-иерархии в том смысле , что для всех I , M [ я ] ⊆ W [ я ] ⊆ M [ я + 1] ; например, задача поиска вершинного покрытия размера k logn в n -вершинном графе с параметром k является полным для M [1]. Гипотеза экспоненциального времени эквивалентна утверждению, что M [1] ≠ FPT , и вопрос о том, M [ i ] = W [ i ] для i  > 1, также открыт. [3]

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

См. Также [ править ]

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

Заметки [ править ]

  1. ^ Например, задача о максимальном независимом множестве для плоских графов является NP-полной, но может быть решена за субэкспоненциальное время. Когда экземпляр 3-САТ размера п сводится к плоской задаче MIS, размер последнего возрастает до порядка thetas ; ( п 2 ), так что экспоненциальная нижняя граница для 3-SAT переводит в нижнюю границучто субэкспоненциальна в расширенный размер экземпляра.
  2. ^ а б в г Woeginger (2003) .
  3. ^ a b Flum & Grohe (2006) .
  4. ^ Калабро, Импальяццо & Патури (2009) .
  5. ^ a b Impagliazzo, Paturi & Zane (2001) .
  6. ^ a b c Патрашку и Уильямс (2010) .
  7. ^ Feige & Kilian (1997) .
  8. ^ а б Чен и др. (2006) .
  9. ^ Карпинский и Schudy (2010)
  10. ^ Cygan et al. (2015)
  11. ^ Lokshtanov, Маркс и Саурабй (2011) .
  12. ^ Цыган, Pilipczuk & Pilipczuk (2013) .

Ссылки [ править ]

  • Калабро, Крис; Impagliazzo, Рассел ; Патури, Рамамохан (2009), «Сложность выполнения схем малой глубины», параметризованные и точные вычисления, 4-й международный семинар, IWPEC 2009, Копенгаген, Дания, 10-11 сентября 2009 г., пересмотренные избранные статьи , стр. 75–85.
  • Чен, Цзианэр; Хуанг, Сючжэнь; Kanj, Iyad A .; Ся, Ге (2006), "Сильные нижние оценки вычислений с помощью параметризованной сложности", Журнал компьютерных и системных наук , 72 (8): 1346–1367, DOI : 10.1016 / j.jcss.2006.04.007.
  • Циган, Марек; Фомин, Федор В .; Ковалик, Лукаш; Локштанов Даниил; Маркс, Даниил; Пилипчук, Марцин; Пилипчук, Михал; Саураб, Сакет (2015), Параметризованные алгоритмы , Springer, стр. 555, ISBN 978-3-319-21274-6
  • Циган, Марек; Пилипчук, Марцин; Пилипчук, Михал (2013), «Известные алгоритмы EDGE CLIQUE COVER, вероятно, оптимальны», Proc. 24-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2013) , arXiv : 1203.1754 , Bibcode : 2012arXiv1203.1754C , заархивировано из оригинала 16 апреля 2013 г. CS1 maint: обескураженный параметр ( ссылка ).
  • Данцин, Евгений; Wolpert, Александр (2010), "На умеренно экспоненциальное время для SAT", Теория и приложения ВЫПОЛНИМОСТЬ тестирования ТВ 2010 , Lecture Notes в области компьютерных наук, 6175 , Springer-Verlag, стр 313-325,. Дои : 10.1007 / 978- 3-642-14186-7_27 , ISBN 978-3-642-14185-0.
  • Файги, Уриил ; Kilian, Джо (1997), "О ограничена по сравнению с полиномиальным недетерминизмом", Чикаго Журнал теоретической информатики , 1 : 1-20, DOI : 10,4086 / cjtcs.1997.001.
  • Флум, Йорг; Grohe, Martin (2006), «16. Субэкспоненциальная управляемость с фиксированными параметрами», Теория параметризованной сложности , Тексты EATCS в теоретической информатике, Springer-Verlag, стр. 417–451, ISBN 978-3-540-29952-3.
  • Impagliazzo, Рассел ; Патури, Рамамохан (1999), «Сложность k-SAT», Proc. 14-я конференция IEEE. на вычислительной сложности , С. 237-240,. DOI : 10.1109 / CCC.1999.766282 , ISBN 978-0-7695-0075-1.
  • Impagliazzo, Рассел ; Патури, Рамамохан; Зейн, Фрэнсис (2001), «Какие проблемы имеют строго экспоненциальную сложность?», Journal of Computer and System Sciences , 63 (4): 512–530, CiteSeerX  10.1.1.66.3717 , doi : 10.1006 / jcss.2001.1774.
  • Карпинский, Марек ; Шуди, Уоррен (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.
  • Локштанов Даниил; Маркс, Даниэль; Саураб, Сакет (2011), «Известные алгоритмы на графах с ограниченной шириной дерева, вероятно, оптимальны», Proc. 22-й симпозиум ACM / SIAM по дискретным алгоритмам (SODA 2011) (PDF) , стр. 777–789, arXiv : 1007.5450 , Bibcode : 2010arXiv1007.5450L , заархивировано из оригинала (PDF) 18 октября 2012 г. , извлечено 05 мая 2011 г. -19.
  • Пэтрашку, Михай ; Уильямс, Райан (2010), "О возможности более быстрых алгоритмов SAT", Proc. 21-й симпозиум ACM / SIAM по дискретным алгоритмам (SODA 2010) (PDF) , стр. 1065–1075 CS1 maint: обескураженный параметр ( ссылка ).
  • Уильямс, Райан (2010), «Улучшение полного перебора предполагает суперполиномиальные нижние границы», Proc. Сорок второй ACM симпозиум по теории вычислений (STOC 2010) , Нью - Йорк, Нью - Йорк, США: АКМ, С. 231-240,. CiteSeerX  10.1.1.216.1299 , DOI : 10,1145 / 1806689,1806723 , ISBN 9781450300506 CS1 maint: обескураженный параметр ( ссылка ).
  • Woeginger, Gerhard (2003), "Точные алгоритмы для NP-сложных задач: обзор", Комбинаторная оптимизация - Eureka, You Shrink! (PDF) , Lecture Notes в области компьютерных наук, 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 CS1 maint: обескураженный параметр ( ссылка ).