Wie können wir "

9
  1. Wie können wir " " als Formel erster Ordnung ausdrücken ?P=PSPACE
  2. Welche Ebene der arithmetischen Hierarchie enthält diese Formel (und welche derzeit bekannte Mindeststufe der Hierarchie enthält sie)?

Als Referenz siehe diesen Blog-Beitrag von Lipton .

Mars
quelle
1
Vielleicht können Sie denselben Lipton-Beweis unter Verwendung eines PSPACE-vollständigen Problems anstelle von SAT in der Definition von und Sie erhalten, dass P P S P A C E als x , c ausgedrückt werden kannψ(x,c,y)PPSPACE dh es ist einSatz Π 2 . Aber IMO ist es eine Art "Hack" ... :-)x,cyψ(x,c,y)Π2
Marzio De Biasi
3
Ich würde mein Leben und alle weltlichen Besitztümer darauf wetten, dass Sie es als "falsch" darstellen können. Das heißt, es ist sogar in der Aussagenlogik ausdrückbar. :)
Shaull
3
@Shaull. Sicher. Und sobald Sie zeigen, dass dies die richtige Darstellung ist, können Sie alle benötigten Besitztümer kaufen. Bitte protestieren Sie nicht, dass der Kommentarbereich zu kurz ist, um einen Beweis zu enthalten.
Vijay D
3
@ VijayD - Ich werde den Köder nehmen: Ich habe einen wirklich wunderbaren Beweis gefunden, und der Kommentarraum ist ausreichend. Aber ich mag die Schrift nicht ...
Shaull

Antworten:

25

Zum einen möchte ich die Kommentare auf die Frage adressieren, wo es wurde vorgeschlagen , dass „false“ drückt , weil die Aussage ist falsch. Während dies ein guter Witz sein mag, ist es tatsächlich sehr schädlich, so zu denken. Wenn wir fragen, wie man einen bestimmten Satz in einem bestimmten formalen System ausdrückt, sprechen wir nicht über Wahrheitswerte. Wenn ja, dann, als jemand fragte: "Wie schreibe ich die Tatsache auf, dass es unendlich viele Primzahlen gibt?" wir könnten mit "3 + 3 = 6" antworten, aber das geht eindeutig nicht. Aus dem gleichen Grund ist "falsch" keine gültige Antwort auf "P=PSPACEP=PSPACE? ". Ich denke, Frege und Russell haben sich sehr bemüht, uns diese Lektion beizubringen. Ok, jetzt zur Antwort.

Lassen Sie mich zeigen, wie man ausdrückt , die andere Richtung ist ähnlich, und dann können Sie sie zu einer Konjunktion zusammenfügen, um P S P A C E = P zu erhalten . In jedem Fall kann es für Ihre Zwecke ausreichen, nur P S P A C E P auszudrücken , je nachdem, was Sie tun.PSPACEPPSPACE=PPSPACEP

Unter Verwendung von Techniken, die denen bei der Konstruktion von Kleenes Prädikat T ähnlich sind , können wir eine begrenzte Quantiferformel konstruieren (die besteht somit in Σ 0 0 = Π 0 0 ) und sagt: "Wenn wir die von k codierte Maschine ausführenund ihre Speicherplatznutzung an | n | m binden, akzeptiert die Maschine die Eingabe n ." Hier | n |acceptspace(k,m,n)Σ00=Π00k|n|mn|n|ist die Länge von . Eine informelle Sichtweise, dass solche Formeln existieren, ist folgende: Wenn k , m und n gegeben sind , können wir die primitive rekursive Grenze berechnen, die davon abhängt, wie viel Zeit und wie viel Raum wir jemals benötigen werden (dh höchstens | n | m Raum und höchstens 2 | n | m Zeit). Wir durchsuchen dann einfach alle möglichen Ausführungsspuren, die innerhalb der berechneten Grenzen liegen - eine solche Suche ist ziemlich ineffizient, aber primitiv rekursiv und kann daher als begrenzte Formel ausgedrückt werden.nkmn|n|m2|n|m

Es gibt eine ähnliche Formel , in dem die Laufzeit durch gebunden ist | n | m .accepttime(k,m,n)|n|m

Betrachten Sie nun die Formel: Es heißt, dass für jede Maschine k die höchstens Platz beansprucht | n | m

k,m.k,m.n.acceptspace(k,m,n)accepttime(k,m,n).
k|n|m gibt es eine Maschine die höchstens | verwendet n | m ' so, dass die beiden Maschinen genau die gleichen n ' s akzeptieren . Mit anderen Worten, die Formel sagt P S P A C E P . Diese Formel lautet Π 0 3 .k|n|mnPSPACEPΠ30

Wir können dies verbessern, wenn wir bereit sind, stattdessen den Satz " ist in Polytime" auszudrücken, der für die meisten Anwendungen gut genug sein sollte, da TQBF PSPACE vollständig ist und daher in Polytime P S P A entspricht C E P . Sei k 0 (der Code von) einer Maschine, die TQBF im Raum erkennt | n | m 0 . Dann kann " T Q B F P " ausgedrückt werden als k ' , m ' .TQBFPSPACEPk0|n|m0TQBFP Diese Formel ist nur Σ 0 2 . Wenn ich ein Komplexitätstheoretiker wäre, würde ich wissen, ob es möglich ist, es noch besser zu machen (aber ich bezweifle es).

k,m.n.acceptspace(k0,m0,n)accepttime(k,m,n).
Σ20
Andrej Bauer
quelle
Ihr erster Absatz ist fast wie eine logische, textuelle Form davon: xkcd.com/169
Vijay D
21

Andrej hat bereits erklärt, dass als Σ 0 2 -Satz geschrieben werden kann. Lassen Sie mich erwähnen, dass diese Klassifizierung in dem Sinne optimal ist, dass diese Tatsache nicht relativiert , wenn die Aussage einem Π 0 2 -Satz entspricht. Genauer gesagt, die Menge der Orakel , aber sie ist durch keine Π 0 2 definierbarP=PSPACEΣ20Π20 so dass P A = P S P A C E A ist, durch eine Σ 0 2 -Formel mit einer freien Variablen zweiter Ordnung A definierbarAPA=PSPACEAΣ20AΠ20 -Formel definierbar. Das Argument wird in den Kommentaren unter /mathpro/57348 beschrieben (für , aber es funktioniert genauso für P S P A C E ) . (Tatsächlich kann man durch eine Ausarbeitung der Idee zeigen, dass die Menge Σ 0 2 -voll im entsprechenden Sinne ist.)P=NPPSPACEΣ20

BEARBEITEN: Der im verknüpften Kommentar angegebene topologische Beweis ist kurz, kann jedoch schwierig erscheinen. Hier ist ein direktes erzwungenes Argument.

kann als Π 0 2 -Formel der Formϕ(A)=x geschrieben werdenPAPSPACEAΠ20 , wobei θ ist Δ 0 0 . Nehmen Sie für den Widerspruch an, dass P A = P.ϕ(A)=xyθ(A,x,y)θΔ00 auch äquivalent zu einer Π 0 2 -Formelψ(A)=x istPA=PSPACEAΠ20 . Fixiere Orakel B , C so, dass P B.ψ(A)=xzη(A,x,z)BC und P C = P S P A C E C .PBPSPACEBPC=PSPACEC

Seit existiert y 0, so dass θ ( B , 0 , y 0 ) . Jedoch θ ein beschränktes Formel ist, daher die Auswertung des Wahrheitswertes θ ( B , 0 , y 0 ) verwendet nur einen endlichen Teil des Oracle. Somit existiert ein endlicher Teil b 0 von B, so dass θ ( A , 0 , y 0 ) für jedes Orakel giltϕ(B)y0θ(B,0,y0)θθ(B,0,y0)b0Bθ(A,0,y0) erweitert b 0 .Ab0

Lassen bezeichnen die Oracle , die sich b 0 , und stimmt mit C , wenn b 0 ist undefiniert. Da P A und P S P A C E A von einer endlichen Änderung des Orakels nicht betroffen sind, haben wir ψ ( C,C[b0]b0Cb0PAPSPACEA . Nach dem gleichen Argument wie oben existiert z 0 und ein endlicher Teil c 0 von C [ b 0 ]ψ(C[b0])z0c0C[b0]so dass für jedes A, das c 0 verlängert . Wir können annehmen , dass c 0 erstreckt b 0 .η(A,0,z0)Ac0c0b0

Auf die gleiche Weise konstruieren wir unendliche Folgen von Zahlen , z 0 , z 1 , z 2 , und endlichen Teilorakelny0,y1,y2,z0,z1,z2, so dassb0c0b1c1b2

  1. für jedes Orakel A, das sich b n erstreckt ,θ(A,n,yn)Abn

  2. für jedes Orakel A, das sich über c n erstreckt .η(A,n,zn)Acn

Nun sei ein Orakel, das alle b n und erstrecktAbn . Dann implizieren 1 und 2, dass ϕ ( A ) und ψ ( A ) gleichzeitig gelten, was der Annahme widerspricht, dass sie Komplemente voneinander sind.cnϕ(A)ψ(A)

Emil Jeřábek
quelle
3
Traurig, dass eine so schöne Antwort auf eine Frage ist, die jetzt geschlossen ist ...
Arnab