Warum ist NP in EXPTIME?

11

Gibt es eine einfache Möglichkeit zu erkennen, warum NP in EXPTIME ist? Es scheint mir a priori denkbar, dass es ein Problem geben könnte, dessen Lösung eine überexponentielle Zeit erfordert, dessen Lösung jedoch in Polynomzeit verifiziert werden könnte.

tparker
quelle
In der Tat NP PSPACE.
Willkommen in der Informatik! Was hast du versucht? Wo bist du festgefahren? Wir wollen nicht nur Ihre (Heim-) Arbeit für Sie erledigen; Wir möchten, dass Sie Verständnis gewinnen. Da wir jedoch nicht wissen, was Ihr zugrunde liegendes Problem ist, können wir nicht anfangen, zu helfen. Sehen Sie hier für eine entsprechende Diskussion. Wenn Sie sich nicht sicher sind, wie Sie Ihre Frage verbessern können, fragen Sie im Computer Science Chat nach . Vielleicht möchten Sie auch unsere Referenzfragen lesen .
Raphael

Antworten:

16

Jedes Problem in NP liegt in EXPTIME, da Sie entweder die exponentielle Zeit verwenden können, um alle möglichen Zertifikate zu testen oder alle möglichen Berechnungspfade einer nicht deterministischen Maschine aufzulisten.

Formal gibt es zwei Hauptdefinitionen von NP . Eine ist, dass eine Sprache  in NP ist, wenn es eine Beziehung  R gibt, so dassLR

  • es ist ein Polynom derart , daß für alle , ,p(x,y)R|y|p(|x|)
  • Mit der Zeichenfolge können wir das inob undx#y|x#y|(x,y)R
  • .L={x(x,y)R}

Wenn wir also eine exponentielle Zeit haben und wissen wollen, ob , können wir einfach alle | ausprobieren Σ | p ( n ) mögliche Werte für ~ y und sehen, ob ( x , y ) R für einen von diesen. Das braucht Zeit 2 O ( p ( n ) ) , also L xL|Σ|p(n)y(x,y)R2O(p(n))LEXPTIME .

Alternativ können wir NP als die Menge von Sprachen definieren, die von nichtdeterministischen Turing-Maschinen mit Polynomzeit bestimmt werden. In diesem Fall sei angenommen, dass  von der Maschine  M in der Zeit p ( n ) für ein Polynom  p für Eingaben der Länge  n bestimmt wird . Dann trifft M  höchstens p ( | x | ) nichtdeterministische Entscheidungen, während bestimmt wird, ob x L ist . Indem wir die Übergangsfunktion von M untersuchen , können wir eine Konstante  k finden, so dass M  höchstens hatLMp(n)pnMp(|x|)xLMkM  nichtdeterministische Auswahlmöglichkeiten bei jedem Schritt der Berechnung (unabhängig von der Eingabe), so dass höchstens k p ( | x | ) = 2 O ( p ( | x | ) ) verschiedene Sequenzen nichtdeterministischer Auswahlmöglichkeiten beim Lesen der Eingabe x vorliegen . Bei gegebener exponentieller Zeit können wir jede dieser Möglichkeiten nacheinander simulieren und sehen, ob eine von ihnen akzeptiert.kkp(|x|)=2O(p(|x|))x

David Richerby
quelle
2
Genau genommen muss das Polynom in der zweiten Kugel ein für alle Mal ausgewählt werden, es kann nicht von und y abhängen . ;)xy
Martin Berger
Was genau ist die Definition von EXPTIME? Ich erinnere mich an , aber Ihre Antwort scheint O ( k p ( | x | ) ) anzunehmen . Es ist nicht offensichtlich, dass das zusätzliche Polynom eingeschlossen werden kann, ohne es zu einer anderen Komplexitätsklasse zu machen. O(k|x|)O(kp(|x|))
Kasperd
3
@kasperd Laut Wikipedia sind EXPTIME die Entscheidungsprobleme, die in gelöst werden können . O(kp(|x|))
Tparker