Существуют ли субэкспоненциальные алгоритмы для NP-полных задач?

51

Существуют ли NP-полные задачи, которые доказали алгоритмы субэкспоненциального времени?

Я спрашиваю об общих входных данных, я не говорю о конкретных особых случаях здесь.

Под субэкспоненциальным я подразумеваю порядок роста над полиномами, но менее экспоненциального, например, . $n^{\log n}$

complexity-theory np-complete np KSB
источник

10

Что вы подразумеваете под «субэкспоненциальным»? Если вы имеете в виду

, ответ определенно да. Если вы имеете в виду

, я считаю, что ответ - нет.

2^{o (n)}

$2^{o(n)}$

2^{n^{o (1)}}

$2^{n^{o(1)}}$

Джефф

57

Зависит от того, что вы подразумеваете под субэкспоненциальным. Ниже я объясню несколько значений «субэкспоненциальный» и что происходит в каждом случае. Каждый из этих классов содержится в классах под ним.

I. $2^{n^{o(1)}}$

Если по subexpoential вы имеете в виду , то гипотеза в теории сложности называется ETH (экспоненциальное время гипотеза) предполагает , что ни один -Жесткой задача может иметь алгоритм с управлением временем . $2^{n^{o(1)}}$ $\mathsf{NP}$ $2^{n^{o(1)}}$

Обратите внимание, что этот класс замкнут относительно композиции с полиномами. Если у нас есть субэкспоненциальная алгоритм времени для любого -Жестких проблем, мы можем объединить его с уменьшением полиномиального времени от SAT ему получить субэкспоненциальную алгоритм 3SAT который нарушал бы ETH. $\mathsf{NP}$

II. , т.е. для всех $\bigcap_{0 < \epsilon} 2^{O(n^\epsilon)}$ $2^{O(n^\epsilon)}$ $0 < \epsilon$

Ситуация похожа на предыдущую.

Он замкнут относительно полиномов, поэтому никакая проблема -hard не может быть решена в это время без нарушения ETH. $\mathsf{NP}$

III. , то есть для некоторых $\bigcup_{\epsilon < 1} 2^{O(n^\epsilon)}$ $2^{O(n^\epsilon)}$ $\epsilon < 1$

Если под субэкспоненциальным вы имеете в виду для некоторого то ответ - да, такие проблемы, несомненно, существуют. $2^{O(n^\epsilon)}$ $\epsilon<1$

Возьмите -полную задачу, такую как SAT. Он имеет алгоритм перебора, который работает за время . Теперь рассмотрим дополненную версию SAT, добавив к входам строку размером : $\mathsf{NP}$ $2^{O(n)}$ $n^k$

S A T^{'} = {⟨ φ, w ⟩ ∣ φ \in S A T and | w | = | φ |^{k}}

$SAT' = \{\langle \varphi,w\rangle \mid \varphi\in SAT \text{ and } |w|=|\varphi|^k \}$

Теперь эта проблема является трудной и может быть решена за время $\mathsf{NP}$ . $2^{O(n^\frac{1}{k})}$

Внутривенно $2^{o(n)}$

Это содержит предыдущий класс, ответ похож.

V. , то есть для всех $\bigcap_{0 < \epsilon}2^{\epsilon n}$ $2^{\epsilon n}$ $\epsilon>0$

Это содержит предыдущий класс, ответ похож.

VI. , то есть для некоторых $\bigcup_{\epsilon < 1}2^{\epsilon n}$ $2^{\epsilon n}$ $\epsilon<1$

Это содержит предыдущий класс, ответ похож.

Что значит субэкспоненциальный?

«Выше полинома» - это не верхняя граница, а нижняя граница, и она называется суперполиномом .

$n^{\lg n}$

$2^{\Theta(n)}$ $2^{n^{\Theta(1)}}$

$\Theta$ $o$ $\epsilon$ $\Theta$ $\epsilon$ $\epsilon>0$ $\Theta$ $\epsilon$ $\epsilon<1$

Какой из них следует назвать субэкспоненциальна спорно. Обычно люди используют тот, который им нужен в своей работе, и называют его субэкспоненциальным.

$\mathsf{Exp}$ $2^{n^{O(1)}}$

$\mathsf{SubExp}$

III используется для алгоритмических верхних границ, подобных тем, которые упомянуты в ответе Пэла.

IV также распространен.

V используется для формулировки гипотезы ETH.

$\mathsf{L}$ $\mathsf{P}$ $\mathsf{NP}$ $\mathsf{PSpace}$ $\mathsf{Exp}$

летний

$\mathsf{NP}$

Кава
источник

7

Этот ответ должен идти в Википедии.

Эрель Сегал-Халеви

32

$2^{O(\sqrt{n} \log n)}n^{O(1)}$ $2^{O(\sqrt{n})}n^{O(1)}$

Набор обратной связи на турнирах [Нога Алон, Даниэль Локштанов, Сакет Саурабх, ALP 2009]
Минимальное заполнение и завершение цепочки [Fomin and Villanger SODA 2012]
Удаление Split Edge [Ghosh et al SWAT 2012]
$t$
Множество проблем двумерности, различные задачи о графах на графах ограниченного рода и особенно планарных графах (см. Demaine, Fomin, Hajiaghayi, Thilikos: Субэкспоненциальные параметризованные алгоритмы на графах графов ограниченного рода и H-минорных свободных )
Параметризованный алгоритм субэкспоненциального времени для дерева Штейнера на плоских графах [Pilipczuk et al STACS 2013]
Тривиально совершенное завершение, пороговое завершение и псевдосплитное завершение [D. и др. STACS 2014]
Завершение интервала [Близнец и др.]
Завершение правильного интервала [Bliznets et al]

Пол Г.Д.
источник

1

2^{O (n^{ϵ})}

$2^{O(n^\epsilon)}$

ϵ < 1

$\epsilon<1$

2^{n^{o (1)}}

$2^{n^{o(1)}}$

Существуют ли субэкспоненциальные алгоритмы для NP-полных задач?

Ответы:

I. 2No ( 1 )2no(1)2^{n^{o(1)}}

II. , т.е. 2 О ( п ε ) для всех 0 < ε⋂0 < ϵ2O ( nε)⋂0<ϵ2O(nϵ)\bigcap_{0 < \epsilon} 2^{O(n^\epsilon)}2O ( nε)2O(nϵ)2^{O(n^\epsilon)} 0 < ϵ0<ϵ0 < \epsilon

III. , то есть 2 О ( п & epsi ; ) для некоторых х < 1⋃ϵ < 12O ( nε)⋃ϵ<12O(nϵ)\bigcup_{\epsilon < 1} 2^{O(n^\epsilon)}2O ( nε)2O(nϵ)2^{O(n^\epsilon)} ϵ < 1ϵ<1\epsilon < 1

Внутривенно 2o(n)2o(n)2^{o(n)}

V. , то есть 2 ϵ n для всех ϵ > 0⋂0<ϵ2ϵn⋂0<ϵ2ϵn\bigcap_{0 < \epsilon}2^{\epsilon n}2ϵn2ϵn2^{\epsilon n} ϵ>0ϵ>0\epsilon>0

VI. , то есть 2 & epsi ; п для некоторых х < 1⋃ϵ<12ϵn⋃ϵ<12ϵn\bigcup_{\epsilon < 1}2^{\epsilon n}2ϵn2ϵn2^{\epsilon n} ϵ<1ϵ<1\epsilon<1

Что значит субэкспоненциальный?

I. $2^{n^{o(1)}}$

II. , т.е. для всех $\bigcap_{0 < \epsilon} 2^{O(n^\epsilon)}$ $2^{O(n^\epsilon)}$ $0 < \epsilon$

III. , то есть для некоторых $\bigcup_{\epsilon < 1} 2^{O(n^\epsilon)}$ $2^{O(n^\epsilon)}$ $\epsilon < 1$

Внутривенно $2^{o(n)}$

V. , то есть для всех $\bigcap_{0 < \epsilon}2^{\epsilon n}$ $2^{\epsilon n}$ $\epsilon>0$

VI. , то есть для некоторых $\bigcup_{\epsilon < 1}2^{\epsilon n}$ $2^{\epsilon n}$ $\epsilon<1$