Einfaches Interpretationsproblem bezüglich der Polynomhierarchie?

8

So NP steht für Probleme , bei denen wir kleine nachprüfbaren Zeugen haben YES - Instanzen und coNP für kleine nachprüfbare Zeugen für NO - Instanzen. Wie funktioniert das?

  1. PNP

  2. NPNP

  3. coNPNP

  4. und so weiter?

T ....
quelle

Antworten:

8

Es gibt eine logische Interpretation der verschiedenen Ebenen der Polynomhierarchie, die die Zeugencharakterisierung von NP und coNP .

Eine Sprache L ist in ΣkP wenn es ein Polytime-Prädikat f und ein Polynom so dass

xL|y1|(|x|)|y2|(|x|)Q|yk|(|x|)f(x,y1,,yk).
Hier:

  • |y|(|x|) bedeutet, dass es eine Zahly deren Länge höchstens(|x|) beträgt,so dass ...
  • |y|(|x|) bedeutet, dass für alley deren Länge höchstens(|x|) beträgt, Folgendes gilt ...
  • Q ist wennk ungerade ist und wennk ist.

In ähnlicher Weise ist L in ΠkP wenn es auf ähnliche Weise geschrieben werden kann, beginnend mit .

Als Beispiel NPNP ist Σ2P und besteht aus allen Sprachen , so dass

xL|y1|(|x|)|y2|(|x|)f(x,y1,,yk).
Als ein anderes BeispielcoNPNP istΠ2P .

Ihr drittes Beispiel ist PNP , was Δ2P . Ich bin mir nicht sicher, was die logische Charakterisierung ist.

Yuval Filmus
quelle
Diese alte MO Post hat einige Charakterisierungen von , obwohl keiner rein logisch erscheinen. Es kann möglich sein, eine davon in einer rein logischen Form zu schreiben. Δ2P
Diskrete Eidechse
@YuvalFilmus Könnten Sie dies zumindest für ausführlicher sein ? NPNP
T ....
1

Zu sagen, dass NP Probleme mit "kleinen nachprüfbaren Zeugen" enthält, ist bestenfalls konzeptionell ungenau. Die Zeugen sind nur polynomiell begrenzt, weil wir wollen, dass der Prüfer effizient ist (dh in Polynomzeit ausgeführt wird). In einer solchen Umgebung kann nur ein polynomiell langes Präfix eines Zeugen relevant sein, weshalb wir auf polynomiell langen Zeugen bestehen. Auch "klein" bedeutet möglicherweise konstant oder logarithmisch; Diese werden natürlich nicht verwendet, weil sie durch Polynom-Zeit-Algorithmen brutal erzwungen werden können (und uns nur Probleme in P ).

Die Art und Weise, wie der Beweissystembegriff von NP verallgemeinert wird, um die Polynomhierarchie zu erhalten, ähnelt dem logischen Standpunkt, den Yuval Filmus in seiner Antwort beschreibt. Lassen Sie mich die weniger technische Sichtweise dahinter vorstellen.

Wir betrachten Zwei-Parteien-Spiele, die auf QBFs basieren. Eine Instanz (oder das "Brett", wenn Sie es sich als Brettspiel wie Schach oder Dame vorstellen möchten) eines solchen Spiels ist eine Formel φ(x1,y1,,xm,ym) und die beiden Spieler, sagen A und B , wählen abwechselnd Werte für xi bzw. yi . Jede solche Wahl ist ein Zug . Wenn keine Werte mehr übrig sind, wird die Formel (dh die endgültige Position des Spiels) ausgewertet. A gewinnt, wenn es wahr ist, undB gewinnt, wenn es falsch ist.

Dieses Spiel modelliert existenzielle und universelle Quantifizierer auf folgende Weise: Wenn die Formel eine echte QBF ist, hat A (das die Rolle existenzieller Quantifizierer spielt) immer eine Gewinnstrategie und kann eine Reihe von x1,,xm auswählen x m die Ursache φ wahr zu sein , um unabhängig von den Werten y1,,ym , aufgenommen durchB (das die Rolle des Allzeichen spielt). Die "Ja" -Instanzen sind diejenigen, in denen der QBF wahr ist, dhA immer eine Gewinnstrategie, unabhängig davon, wieB spielt.

Σi undΠi entsprechen dann Spielen, die füri Zügedauernund in denenA bzw.B zuerst gehen dürfen. Tatsächlich erhalten Sie sogarPSPACE und die Aufnahme vonPHPSPACE als Bonus, da dies der Klasse von Spielen entspricht, die für eine beliebige (wenn auch vorgegebene) Anzahl von Zügen ausgeführt werden.

Beachten Sie auch, dass Σ1=NP und Π1=coNP eher entartete Fälle dieser Spiele sind, da B bzw. A überhaupt keine Chance haben, sich zu bewegen! Zum Beispiel für die "Ja" -Instanzen von Π1=coNP ,A bekommt einfach zu gewinnenindemnichtstun (da eine „Ja“ Instanz eine Tautologie ist und wahr istunabhängig davonwelcheB wählt).

Es gibt auch eine allgemeinere Version des oben genannten, die auf generischen Spielen basiert (und nicht speziell auf QBFs). Sie finden es beispielsweise in Abschnitt 5.4 "PSPACE and Games" von Goldreichs "Computational Complexity: A Conceptual Perspective" ( hier ist ein kostenloser Link zum Entwurf der Version; siehe S. 174 sowie S. 118–121). .

dkaeae
quelle
Vielen Dank. Wie spiegeln die Spieleigenschaften , N P N P und c o N P N P wider (wie gibt es für jede Bewegung, die A macht oder so etwas, einen Zeugen mit kurzer Polynomlänge ?)PNPNPNPcoNPNPA
T ....
In der generischen Version aus dem Goldreich-Buch, die ich erwähnt habe, finden Sie, dass wir die folgenden Besonderheiten benötigen: 1. "Jeder Zug hat eine Beschreibungslänge, die durch ein Polynom in der Länge der Anfangsposition begrenzt ist "; 2. Die Aktualisierung der aktuellen Position kann in Polynomzeit erfolgen (bzw. in Bezug auf die Länge der Anfangsposition). 3. Die Bestimmung des Gewinners aus der endgültigen Position benötigt Polynomzeit. Diese werden alle vom QBF-Spiel erfüllt.
dkaeae
"Die Zeugen [für NP] sind nur polynomiell begrenzt, weil wir wollen, dass der Verifizierer effizient ist (dh in Polynomzeit ausgeführt wird)." Das ist nicht wirklich wahr. Die Überprüfung erfolgt in Polynomzeit in Bezug auf die Länge des Zeugen, sodass der Zeuge unabhängig von seiner Dauer "effizient" überprüfbar ist. Wir fordern, dass der Zeuge polynomiell begrenzt ist, da dies der polynomiellen Zeitgrenze des nichtdeterministischen TM entspricht, das der Zeuge beobachtet.
David Richerby
@DavidRicherby Tatsächlich ist es für (offline) nichtdeterministische TMs unerheblich, ob die nichtdeterministische Eingabe überhaupt begrenzt ist oder nicht (dh eine unendliche Zeichenfolge). In dieser Einstellung ist die Menge von Problemen, die in einer polynomiellen Anzahl von Schritten in der Länge der Eingabe entscheidbar sind. Dass dies auch ein Polynom in der Anzahl der verwendeten nichtdeterministischen Bits ist, ist ein (wünschenswerter) Nebeneffekt. Für Online-Nichtdeterminismus umso mehr. Die Zeugenlänge wird durch die gebundene Zeit bestimmt, nicht umgekehrt. NP
dkaeae
1
@ThomasKlimpel In der Tat meinte ich . Vielen Dank für den Hinweis. Vielen Dank auch für die aufschlussreiche Antwort. Mir war nicht bewusst, dass es eine (zumindest teilweise) "schöne" logische Charakterisierung von Δ i gab (und in der Literatur keine finden konnte) +1ΣiΔi
dkaeae
1

PNP ist das Schließen vonNP unter Polynomzeit Turing-Reduktionen (= Cook-Reduktionen). Daher ist es unter Cook-Reduktionen geschlossen, so dass wirPNP=PPNP . InTat, für jedes OrakelA definieren wirPA als die Schließung vonA unter CookReduzierungen, und wir haben immerPA=PPA undNPA=NPPA . Auch coNPA=coNPPA undPNP=PcoNP . Aber Kochreduktionen fühlen sich für Entscheidungsprobleme etwas unnatürlich an.

Es ist zu beachten, dass P eine Funktionsklasse in Verkleidung ist und dass PNP auch eine Funktionsklasse in Verkleidung ist. Schreiben wir PF für die Klasse der polynomialzeitberechnbaren Teilfunktionen, dh die Funktionsklasse, die P , und PFNP für die Funktionsklasse, die PNP . Das Einbeziehen der Teilfunktionen ermöglicht die Verwendung einer etablierten Notation (verwendet in Eine Taxonomie von Komplexitätsklassen von Funktionen von A. Selman, 1994), die den Namenskonflikt mit der nicht verwandten Klasse FP vermeidet .

Kochreduktion fühlt sich für Funktionsklassen natürlicher an. Sie sind wahrscheinlich auf eine Cook-Reduktion gestoßen (und implizit auch auf die Klasse PFNP ), als Ihr Lehrbuch oder Professor erklärte, warum es in Ordnung ist, nur Entscheidungsprobleme zu betrachten. Typischerweise wird so etwas wie ein Algorithmus (von PFNP ) zur Berechnung der lexikographisch letzten zufriedenstellenden Zuordnung einer gegebenen SAT-Instanz beschrieben. Man fragt zuerst das Orakel, ob es überhaupt eine zufriedenstellende Zuordnung gibt, und bestimmt dann die Werte der (binären) Variablen xk indem man das Orakel nacheinander fragt, ob es eine zufriedenstellende Zuordnung gibt, wobei x1,,xk1 are set to the already determined values, and xk is set to 1. If yes, then one sets xk to 1, otherwise one sets xk to 0. (Note that this is a partial function, since the function is undefined in case there is no satisfying assignment.)


Let me try to say some words about Yuval Filmus remark:

Your third example is PNP, which is Δ2P. I'm not sure what is the logical characterization.

There are two difficulties to overcome: (1) the characterization of a function class has a different feel than the logical characterization of a decision class, and (2) at least for PA we have to model the deterministic character of the queries to the oracle A.

If we look at the class UPF of partial functions corresponding to the class UP of decision problems first, then we can ignore (2) for a moment: A partial function pf is in UPFΣkP if there is a polytime partial function p, a polytime predicate f and a polynomial such that pf(x)=p(x,z) where

1|z|(|x|)p(x,z)|y1|(|x|)|y2|(|x|)Q|yk|(|x|)f(x,y1,,yk,z).
Here:

  • |y|(|x|) means that there exists a number y whose length is at most (|x|) such that ...
  • |y|(|x|) mean that for all y whose length is at most (|x|), the following holds ...
  • Q is if k is odd and if k is even.

One could try to overcome (2) by introducing the operators BIT(z,i):=z[i] and TRUNC(z,i):=z|[1,i). But it would still get ugly, and one can argue whether this would really constitute a logical characterization.

Thomas Klimpel
quelle