Gibt es subexponentielle Zeitalgorithmen für NP-vollständige Probleme?

51

Gibt es NP-vollständige Probleme, bei denen sich Algorithmen mit subexponentieller Zeit bewährt haben?

Ich bitte um die allgemeinen Eingaben für den Fall, ich spreche hier nicht über nachvollziehbare Sonderfälle.

Mit subexponentiell meine ich eine Wachstumsordnung über Polynomen, aber weniger als exponentiell, zum Beispiel .nlogn

ksb
quelle
10
Was meinst du mit "subexponentiell"? Wenn Sie meinen , lautet die Antwort definitiv ja. Wenn Sie meinen , 2 n o ( 1 ) , glaube ich, ist die Antwort nein. 2o(n)2no(1)
JeffE

Antworten:

57

Kommt darauf an, was Sie mit subexponentiell meinen. Nachfolgend erkläre ich einige Bedeutungen von "subexponentiell" und was jeweils passiert. Jede dieser Klassen ist in den Klassen darunter enthalten.


I. 2no(1)

2no(1)NP2no(1)

NP

0<ϵ2O(nϵ)2O(nϵ) 0<ϵ

Die Situation ist ähnlich wie bei der vorherigen.

NP


ϵ<12O(nϵ)2O(nϵ) ϵ<1

2O(nϵ)ϵ<1

NP2O(n)nk

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

NP2O(n1k)

2o(n)

Dies enthält die vorherige Klasse, die Antwort ist ähnlich.

0<ϵ2ϵn2ϵn ϵ>0

Dies enthält die vorherige Klasse, die Antwort ist ähnlich.

ϵ<12ϵn2ϵn ϵ<1

Dies enthält die vorherige Klasse, die Antwort ist ähnlich.


Was bedeutet subexponentiell?

"Über Polynom" ist keine Obergrenze, sondern eine Untergrenze und wird als Superpolynom bezeichnet .

nlgn

2Θ(n)2nΘ(1)

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

Welches man subexponentiell nennen soll, ist fraglich. Normalerweise verwenden die Menschen die, die sie für ihre Arbeit benötigen, und bezeichnen sie als subexponentiell.

Exp2nO(1)

SubExp

III wird für algorithmische Obergrenzen verwendet, wie sie in Pals Antwort erwähnt wurden.

IV ist auch üblich.

Mit V wird die ETH-Vermutung angegeben.

LPNPPSpaceExp

Sommerlich

NP

Kaveh
quelle
7
Diese Antwort sollte an Wikipedia gehen.
Erel Segal-Halevi
32

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

Pål GD
quelle
1
2O(nϵ)ϵ<12no(1)