Warum ist NP in EXPTIME?

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.

complexity-theory complexity-classes tparker
quelle

In der Tat NP PSPACE.

\subseteq

$\subseteq$

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

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 so dass $L$ $R$

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

Wenn wir also eine exponentielle Zeit haben und wissen wollen, ob , können wir einfach alle ausprobieren mögliche Werte für ~ und sehen, ob für einen von diesen. Das braucht Zeit , also $x\in L$ $|\Sigma|^{p(n)}$ $y$ $(x,y)\in R$ $2^{O(p(n))}$ $L\in\,$ EXPTIME .

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 in der Zeit für ein Polynom für Eingaben der Länge . Dann höchstens nichtdeterministische Entscheidungen, während bestimmt wird, ob . Indem wir die Übergangsfunktion von untersuchen , können wir eine Konstante so dass höchstens hat $L$ $M$ $p(n)$ $p$ $n$ $M$ $p(|x|)$ $x\in L$ $M$ $k$ $M$ nichtdeterministische Auswahlmöglichkeiten bei jedem Schritt der Berechnung (unabhängig von der Eingabe), so dass höchstens verschiedene Sequenzen nichtdeterministischer Auswahlmöglichkeiten beim Lesen der Eingabe vorliegen . Bei gegebener exponentieller Zeit können wir jede dieser Möglichkeiten nacheinander simulieren und sehen, ob eine von ihnen akzeptiert. $k$ $k^{p(|x|)} = 2^{O(p(|x|))}$ $x$

David Richerby
quelle

Genau genommen muss das Polynom in der zweiten Kugel ein für alle Mal ausgewählt werden, es kann nicht von

und

abhängen . ;)

x

$x$

y

$y$

Martin Berger

Was genau ist die Definition von EXPTIME? Ich erinnere mich an

, aber Ihre Antwort scheint

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(k^{|x|})$

O (k^{p (| x |)})

$O(k^{p(|x|)})$

Kasperd

@kasperd Laut Wikipedia sind EXPTIME die Entscheidungsprobleme, die in

gelöst werden können .

O (k^{p (| x |)})

$O(k^{p(|x|)})$

Tparker

Warum ist NP in EXPTIME?

Antworten: