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

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

Определение

k-СИДЕЛ проблема проверки того, Логическое выражение, в конъюнктивная нормальная форма максимум с k переменных на предложение, можно сделать истинным, присвоив его переменным логические значения. Для каждого целого числа k ≥ 2, определите действительное число sk быть инфимум действительных чисел δ, для которых k-SAT может быть решена алгоритмически за время O (2δп), куда п количество переменных в данном k-SAT экземпляр. потом s2 = 0, потому что 2-СБ можно решить в полиномиальное время. Более того, s3 ≤ s4 ≤ ..., так как сложность не уменьшается с ростом k.

В гипотеза экспоненциального времени это догадка который sk > 0 для каждого k > 2, или, что то же самое, s3 > 0.

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

Потому что числа s3, s4, ... сформировать монотонная последовательность ограниченный сверху единицей, они должны сходиться к пределу s∞. В гипотеза сильного экспоненциального времени (SETH) - это гипотеза о том, что s∞=1.[4]

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

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

Это невозможно для sk в равной s∞ для любого конечного k: в качестве Импальяццо, Патури и Зейн (2001) показал, что существует постоянная α такой, что sk ≤ s∞(1 − α/k). Следовательно, если гипотеза экспоненциального времени верна, должно быть бесконечно много значений k для которого sk отличается от sk + 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

  1. ^ Например, Задача о максимальном независимом множестве для плоских графов является NP-полной, но может быть решена за субэкспоненциальное время. Когда экземпляр 3-SAT размера п сводится к плоской задаче МИС, размер последней возрастает до порядка Θ (п2), поэтому экспоненциальная нижняя граница для 3-SAT преобразуется в нижнюю границу, которая является субэкспоненциальной для расширенного размера экземпляра.
  2. ^ а б c d Woeginger (2003).
  3. ^ а б Flum & Grohe (2006).
  4. ^ Калабро, Импальяццо и Патури (2009).
  5. ^ а б Импальяццо, Патури и Зейн (2001).
  6. ^ а б c Патрашку и Уильямс (2010).
  7. ^ Файги и Килиан (1997).
  8. ^ а б Chen et al. (2006).
  9. ^ Карпинский и Шуди (2010)
  10. ^ Cygan et al. (2015)
  11. ^ Локштанов, Маркс и Саураб (2011).
  12. ^ Cygan, Pilipczuk и Pilipczuk (2013).

Рекомендации

  • Калабро, Крис; Импальяццо, Рассел; Патури, Рамамохан (2009), "Сложность выполнения схем малой глубины", Параметризованные и точные вычисления, 4-й международный семинар, IWPEC 2009, Копенгаген, Дания, 10-11 сентября 2009 г., отредактированные избранные статьи, стр. 75–85.
  • Чен, Цзианэр; Хуан, Сючжэнь; Kanj, Iyad A .; Ся, Ге (2006), "Сильные нижние оценки вычислений с помощью параметризованной сложности", Журнал компьютерных и системных наук, 72 (8): 1346–1367, Дои: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, заархивировано из оригинал на 2013-04-16.
  • Данцин, Евгений; Вольперт, Александр (2010), "Об умеренно экспоненциальном времени для SAT", Теория и приложения тестирования выполнимости - SAT 2010, Конспект лекций по информатике, 6175, Springer-Verlag, стр. 313–325, Дои:10.1007/978-3-642-14186-7_27, ISBN  978-3-642-14185-0.
  • Файги, Уриэль; Килиан, Джо (1997), "Об ограниченном и полиномиальном недетерминизме", Чикагский журнал теоретической информатики, 1: 1–20, Дои:10.4086 / cjtcs.1997.001.
  • Флум, Йорг; Grohe, Мартин (2006), «16. Субэкспоненциальная управляемость с фиксированными параметрами», Параметризованная теория сложности, Тексты EATCS в теоретической информатике, Springer-Verlag, стр. 417–451, ISBN  978-3-540-29952-3.
  • Импальяццо, Рассел; Патури, Рамамохан (1999), «Сложность k-SAT», Proc. 14-я конференция IEEE Conf. по вычислительной сложности, стр. 237–240, Дои:10.1109 / CCC.1999.766282, ISBN  978-0-7695-0075-1.
  • Impagliazzo, Рассел; Патури, Рамамохан; Зейн, Фрэнсис (2001), «Какие проблемы имеют сильно экспоненциальную сложность?», Журнал компьютерных и системных наук, 63 (4): 512–530, CiteSeerX  10.1.1.66.3717, Дои:10.1006 / jcss.2001.1774.
  • Карпинский, Марек; Шуди, Уоррен (2010), «Более быстрые алгоритмы для турнира по набору арок с обратной связью, турнира по агрегированию рангов Кемени и турниру по взаимопониманию», Proc. ISAAC 2010, часть I, Конспект лекций по информатике, 6506: 3–14, arXiv:1006.4396, Дои: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) на 2012-10-18, получено 2011-05-19.
  • Пэтрашку, Михай; Уильямс, Райан (2010), «О возможности более быстрых алгоритмов SAT», Proc. 21-й симпозиум ACM / SIAM по дискретным алгоритмам (SODA 2010) (PDF), стр. 1065–1075.
  • Уильямс, Райан (2010), «Улучшение полного перебора подразумевает суперполиномиальные нижние оценки», Proc. 42-й симпозиум ACM по теории вычислений (STOC 2010), Нью-Йорк, Нью-Йорк, США: ACM, стр. 231–240, CiteSeerX  10.1.1.216.1299, Дои:10.1145/1806689.1806723, ISBN  9781450300506.
  • Woeginger, Герхард (2003), «Точные алгоритмы для NP-сложных задач: обзор», Комбинаторная оптимизация - Эврика, сжимайся! (PDF), Конспект лекций по информатике, 2570, Springer-Verlag, стр. 185–207, CiteSeerX  10.1.1.168.5383, Дои:10.1007/3-540-36478-1_17, ISBN  978-3-540-00580-3.