Folgen von NP = PSPACE

Was wären die schlimmen Folgen von NP = PSPACE? Ich bin überrascht, dass ich dazu nichts gefunden habe, da diese Klassen zu den berühmtesten gehören.

Hätte dies insbesondere Konsequenzen für die unteren Schichten?

Wenn , würde dies bedeuten:$\mathsf{NP} = \mathsf{PSPACE}$

• N $\mathsf{P^{\#P}} = \mathsf{NP}$
  Das heißt, das Zählen der Lösungen für ein Problem in wäre vielfach reduzierbar, um eine einzige Lösung zu finden.$\mathsf{NP}$

• $\mathsf{PP} = \mathsf{NP}$
  Das heißt, polynomzeit-randomisierte Algorithmen mit einer Erfolgswahrscheinlichkeit von beliebig nahe 1/2 sind polynomzeitreduzierbar auf polynomzeit-randomisierte Algorithmen mit einseitigem Fehler, bei denen JA-Instanzen akzeptiert werden mit beliebig geringer Wahrscheinlichkeit;

• $\mathsf{MA} = \mathsf{NP}$
  Das heißt, für jedes Problem, das in der Polynomzeit überprüfbar ist, liefert die Randomisierung bestenfalls eine Beschleunigung der Polynomzeit (dies ist jedoch nur eine Folge der Kollapsierung der Polynomzeithierarchie).

• $\mathsf{BQP} \subseteq \mathsf{NP}$
  Das heißt, jedes Problem, das von einem Quantencomputer gelöst werden kann, hat leicht Zertifikate für seine Antworten verifiziert. Dies wäre ein wichtiges positives Ergebnis in der Philosophie der Quantenmechanik und wahrscheinlich hilfreich für die Bemühungen, Quantencomputer zu konstruieren (um zu überprüfen, ob sie das tun, was sie tun sollen).

All dies liegt an den Containments der Klassen auf der linken Seite in (obwohl wir auch ).B Q P ⊆ P $\mathsf{PSPACE}$$\mathsf{BQP \subseteq PP}$

Ein Punkt, der implizit, aber noch nicht explizit erwähnt wurde, ist, dass wir . Obwohl dies gleichbedeutend ist mit zu , folgt dies direkt aus der Tatsache, dass unter complement geschlossen ist, was trivial zu beweisen ist.P H N P P S P A C $\mathsf{NP} = \mathsf{coNP}$$\mathsf{PH}$$\mathsf{NP}$$\mathsf{PSPACE}$

Ich denke, ist es wert, allein darauf hinzuweisen, da es eine große Anzahl überraschender Konsequenzen gibt: Es gibt kurze Beweise, wenn ein Graph nicht dreifarbig ist, * nicht-* Hamiltonianer Wenn zwei Graphen * nicht * isomorph sind, ... und (in gewissem Sinne allgemeiner) gibt es ein Cook-Reckhow-Beweissystem, in dem jede Satz-Tautologie einen polynomgroßen Beweis hat.$\mathsf{NP} = \mathsf{coNP}$

If${\bf NP} = {\bf PSPACE}$

1) Die Polynom-Hierarchie würde zu .${\bf NP }$

2) Wir werden jetzt da wir wissen, dassP S P A C E ≠ N ${\bf NP } \not ={\bf NL}$${\bf PSPACE} \not = {\bf NL}$

---AKTUALISIEREN---

3) Es ist bekannt, dass , wobei es sich um die logarithmisch raumbegrenzten Versionen von , bzw. . Dann könnte per Definition keine dieser Komplexitätsklassen gleich unter der Annahme, dass .N P C = P P P N P N P = P S P A C ${\bf NL} \subseteq {\bf C_=L} \subseteq {\bf PL}$${\bf NP}$${\bf C_=P}$${\bf PP}$${\bf NP}$${\bf NP} = {\bf PSPACE}$

Zusätzlich zu den Ergebnissen in allen anderen Antworten darauf gibt es ein ein Interactive Proof - Systeme beteiligt ( ), dass die Verallgemeinerung ist wo Verifier und Prover tauschen Nachrichten aus, um die Sprache zu erkennen.N ${\bf IP}$${\bf NP}$

Es ist bekannt, dass , wenn also , bedeutet dies, dass nur eine Nachricht ausreicht! Für mich ist das beeindruckendere an diesem Ergebnis, dass der Prüfer den Prüfer nicht herausfordern müsste und der allerersten von ihr gesendeten Nachricht vertrauen kann.N P = P S P A C ${\bf IP = PSPACE}$${\bf NP = PSPACE}$