NEXPTIME

Im Computerkomplexitätstheorie, das Komplexitätsklasse Nexptime (manchmal genannt Nexp) ist der Satz von Entscheidungsprobleme das kann durch a gelöst werden Nichtdeterministische Turing-Maschine Zeit verwenden .

Bezüglich NtzeitAnwesend

Alternative, Nexptime kann unter Verwendung deterministischer Turing -Maschinen als Verifizierer definiert werden. EIN Sprache L ist in Nexptime Wenn und nur wenn es Polynome gibt p und qund eine deterministische Turing -Maschine M, so dass

  • Für alle x und y, Die Maschine M läuft rechtzeitig auf Eingabe
  • Für alle x in LEs gibt eine Schnur y von Länge so dass
  • Für alle x nicht in L und alle Saiten y von Länge ,

Wir wissen

PNp ⊆ Exptime ⊆ Nexptime

und auch durch die Zeithierarchie Theorem, das

NP ⊊ Nexptime

Wenn P = np, dann Nexptime = expime (Polsterargument); etwas präziser, ENe Wenn und nur wenn es existiert spärliche Sprachen in Np das sind nicht in P.[1]

Alternative Charakterisierungen

Nexptime oft entsteht im Kontext von Interaktive Proof -Systeme, wo es zwei Hauptcharakterisierungen davon gibt. Das erste ist das MIP Proof-System, bei dem wir zwei allmächtige Provers haben, die mit einem randomisierten Polynomzeitprüfer (aber nicht miteinander) kommunizieren. Wenn sich die Saite in der Sprache befindet, müssen sie in der Lage sein, den Überprüfer davon mit hoher Wahrscheinlichkeit zu überzeugen. Wenn sich die Zeichenfolge nicht in der Sprache befindet, dürfen sie den Überprüfer nicht gemeinsam dazu bringen, die Zeichenfolge zu akzeptieren, außer mit geringer Wahrscheinlichkeit. Die Tatsache, dass MIP Proof -Systeme können jedes Problem in lösen Nexptime ist ziemlich beeindruckend, wenn wir bedenken, dass wir, wenn nur ein Prover vorhanden ist, nur alle erkennen können PSPACE; Die Fähigkeit des Verifizierers, den beiden Provers zu "kreuzen", verleiht ihm große Kraft. Sehen Interaktives Proof -System#MIP für mehr Details.

Ein weiteres interaktives Proof -System charakterisiert Nexptime ist eine bestimmte Klasse von Probabilistisch prüfbare Beweise. Erinnere dich daran Np Kann als die Klasse von Problemen angesehen werden, bei denen ein allmächtiger Prover einen angeblichen Beweis gibt, dass sich eine Zeichenfolge in der Sprache befindet, und eine deterministische Polynomzeitmaschine überprüft, ob es sich um einen gültigen Beweis handelt. Wir nehmen zwei Änderungen an diesem Setup vor:

  • Fügen Sie die Zufälligkeit hinzu, die Fähigkeit, Münzen umzudrehen, der Verifiermaschine.
  • Anstatt einfach den angeblichen Beweis für den Überprüfer auf einem Band zu geben, geben Sie ihm einen zufälligen Zugriff auf den Beweis. Der Überprüfer kann einen Index in die Proof -Zeichenfolge angeben und das entsprechende Bit empfangen. Da der Verifizierer einen Index der Polynomlänge schreiben kann, kann er möglicherweise in eine exponentiell lange Beweiszeichenfolge indexiert werden.

Diese beiden Erweiterungen erweitern die Leistung des Proof -Systems stark und ermöglichen es, alle Sprachen in zu erkennen Nexptime. Die Klasse heißt PCP(Poly, Poly). In dieser Charakterisierung kann der Überprüfer nur darauf beschränkt sein, nur eine konstante Anzahl von Bits zu lesen, d. H. Nexptime = PCP(Poly, 1). Sehen Probabilistisch prüfbare Beweise für mehr Details.

Nexptime-Complete

Ein Entscheidungsproblem ist nexptime-komplett, wenn es in Nexptime ist, und jedes Problem in Nexptime hat eine Polynomzeit viele eins Reduktion dazu. Mit anderen Worten, es gibt eine Polynomzeit Algorithmus Das verwandelt Instanzen von einem in Fälle des anderen mit der gleichen Antwort. Probleme, die nexptime sind, könnten als die schwierigsten Probleme in der Nexptime angesehen werden. Wir wissen, dass Nexptime-Complete-Probleme nicht in NP sind; Es wurde nachgewiesen, dass diese Probleme nicht verifiziert werden können Polynomzeit, bis zum Zeithierarchie Theorem.

Ein wichtiger Satz von Nexptime-Complete -Probleme beziehen sich auf prägnante Schaltkreise. Vorbereitete Schaltkreise sind einfache Maschinen, mit denen Grafiken in exponentiell weniger Raum beschrieben werden. Sie akzeptieren zwei Scheitelpunktzahlen als Eingang und Ausgabe, ob zwischen ihnen eine Kante besteht. Wenn Sie ein Problem in einer Grafik in einer natürlichen Darstellung lösen, wie z. Adjazenzmatrix, ist NP-Completeund dann das gleiche Problem auf eine prägnante Schaltungsdarstellung zu lösen, ist Nexptime-Complete, da der Eingang exponentiell kleiner ist (unter einer leichten Bedingung, dass die NP-Abschlussreduktion durch eine "Projektion" erreicht wird).[2][3] Als ein einfaches Beispiel, um a zu finden Hamiltonianischer Weg für eine so codierte Grafik ist Nexptime-Komplett.

Siehe auch

Verweise

  1. ^ Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse-Sets in NP-P: Exptime gegen Nexptime. Informationen und Kontrolle, Band 65, Ausgabe 2/3, S. 158–181. 1985. In der ACM Digital Library
  2. ^ C. Papadimitriou & M. Yannakakis, Eine Notiz zu prägnanten Darstellungen von Graphen, Information and Control, Vol 71 Num 3, Décember 1986, S. 181—185, doi:10.1016/s0019-9958 (86) 80009-2
  3. ^ C. Papadimitriou. Rechenkomplexität Addison-Wesley, 1994. ISBN0-201-53082-1. Abschnitt 20.1, S.492.