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

51

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

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

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

KSB
источник
10
Что вы подразумеваете под «субэкспоненциальным»? Если вы имеете в виду , ответ определенно да. Если вы имеете в виду 2 n o ( 1 ) , я считаю, что ответ - нет. 2o(n)2no(1)
Джефф

Ответы:

57

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


I. 2no(1)

Если по subexpoential вы имеете в виду , то гипотеза в теории сложности называется ETH (экспоненциальное время гипотеза) предполагает , что ни один N P -Жесткой задача может иметь алгоритм с управлением временем 2 н O ( 1 ) .2no(1)NP2no(1)

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

II. , т.е. 2 О ( п ε ) для всех 0 < ε0<ϵ2O(nϵ)2O(nϵ) 0<ϵ

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

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


III. , то есть 2 О ( п & epsi ; ) для некоторых х < 1ϵ<12O(nϵ)2O(nϵ) ϵ<1

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

Возьмите -полную задачу, такую ​​как SAT. Он имеет алгоритм перебора, который работает за время 2 O ( n ) . Теперь рассмотрим дополненную версию SAT, добавив к входам строку размером n k :NP2O(n)nk

SAT={φ,wφSAT and |w|=|φ|k}

Теперь эта проблема является трудной и может быть решена за время 2 O ( n 1NP.2O(n1k)

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

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

V. , то есть 2 ϵ n для всех ϵ > 00<ϵ2ϵn2ϵn ϵ>0

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

VI. , то есть 2 & epsi ; п для некоторых х < 1ϵ<12ϵn2ϵn ϵ<1

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


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

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

nlgn

2Θ(n)2nΘ(1)

ΘoϵΘϵϵ>0Θϵϵ<1

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

Exp2nO(1)

SubExp

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

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

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

LPNPPSpaceExp

летний

NP

Кава
источник
7
Этот ответ должен идти в Википедии.
Эрель Сегал-Халеви
32

2O(nlogn)nO(1)2O(n)nO(1)

Пол Г.Д.
источник
1
2O(nϵ)ϵ<12no(1)