Folgen von und ?

Wir wissen, dass wenn ist, der gesamte PH zusammenbricht. Was ist, wenn die Polynomhierarchie teilweise zusammenbricht? (Oder wie kann man verstehen, dass PH über einem bestimmten Punkt und nicht unter einem bestimmten Punkt zusammenbrechen kann?)$P=NP$

Mit kürzeren Worten, was wären die Konsequenzen von und ?P ≠ N $NP=coNP$$P\ne NP$

Für mich ist eine der grundlegendsten und überraschendsten Konsequenzen von das Vorhandensein kurzer Beweise für eine ganze Reihe von Problemen, bei denen es sehr schwierig ist zu erkennen, warum sie kurze Beweise haben sollten. (Dies ist eine Art Rückschritt von "Welche anderen Auswirkungen auf die Komplexität hat dieser Zusammenbruch?" Zu "Was sind die grundlegenden, bodenständigen Gründe, warum dieser Zusammenbruch überraschend wäre?")$\mathsf{NP}=\mathsf{coNP}$

Wenn beispielsweise ist, gibt es für jeden Graphen, der nicht Hamilton ist, einen kurzen Beweis für diese Tatsache. Ähnliches gilt für Diagramme, die nicht dreifarbig sind. Ähnliches gilt für Paare von Graphen, die nicht isomorph sind. Ähnliches gilt für jede Satztautologie .$\mathsf{NP}=\mathsf{coNP}$

In einer Welt, in der , besteht die Schwierigkeit beim Nachweis von nicht darin, dass einige kurze Tautologien lange Beweise haben - denn in einer solchen Welt hat jede Tautologie ein Polynom Kurzer Beweis - sondern dass es einen anderen Grund gibt, warum wir diese Beweise nicht effizient finden können.$\mathsf{P} \neq \mathsf{NP} = \mathsf{coNP}$

Wenn wir auch annehmen , würde die Hypothese auch den Zusammenbruch randomisierter Klassen verursachen:$\mathsf{NP}=\mathsf{RP}$ . Obwohl vermutet wird, dass diese alle bedingungslos in P zusammenbrechen , ist noch offen, ob dies tatsächlich geschieht. In jedem Fallscheint N P = c o N P an sich nicht zu implizieren, dass diese randomisierten Klassen zusammenbrechen.$\,\,\mathsf{ZPP}=\mathsf{RP}=\mathsf{CoRP}=\mathsf{BPP}$$\mathsf{P}$$\mathsf{NP}=co\mathsf{NP}$

Wenn dies nicht der Fall ist, dh wir haben zumindest , dann hätte dies zusammen mit der Hypothese N P = c o N P eine weitere wichtige Konsequenz:$\mathsf{BPP}\neq \mathsf{P}$$\mathsf{NP}=co\mathsf{NP}$ . Dies ergibtaus einer Folge von Babai, Fortnow, Nisan und Wigderson, die besagtdasswenn alle unären (tally) Sprachen in P H fallen in P , dann B P P = P . Wenn also B P P ≠ P ist , können sie nicht alle in P fallen , da dieAnnahme N P = c o N P P H = N P impliziert. Daher muss es in N P - P eine Zählsprache geben$\,\,\mathsf{E}\neq \mathsf{NE}$$\mathsf{PH}$$\mathsf{P}$$\mathsf{BPP}=\mathsf{P}$$\mathsf{BPP}\neq \mathsf{P}$$\mathsf{P}$$\mathsf{NP}=co\mathsf{NP}$$\mathsf{PH}=\mathsf{NP}$$\mathsf{NP}-\mathsf{P}$. Schließlich ist bekannt, dass das Vorhandensein einer Tally-Sprache in E ≠ N E impliziert .$\mathsf{NP}-\mathsf{P}$$\mathsf{E}\neq \mathsf{NE}$

Die obige Überlegung zeigt den interessanten Effekt, dass die Hypothese , obwohl sie ein Kollaps ist, tatsächlich die Trennkraft von B P P ≠ P verstärkt , da nicht bekannt ist, dass letztere allein E ≠ N E impliziert . Diese "Anomalie" scheint die Vermutung B P P = P zu stützen .$\mathsf{NP}=co\mathsf{NP}$$\mathsf{BPP}\neq \mathsf{P}$$\mathsf{E}\neq \mathsf{NE}$$\mathsf{BPP}= \mathsf{P}$

${\bf \#P}$

${ \rm \underline {Valiant's-Definition:}}$$C$$\#C =\cup_{A\in C}(\#P)^{A}$$({\#P}^A)$$A$

${\bf \#NP} = {\bf \#CoNP}$

${ \rm \underline {Toda's-Definition:}}$$C$$\# .C$$f$$C-$$R$$p$$x$$f(x)=||\{y|p(|x|)=|y|$$R(x,y)\}||$

${\bf \#.NP} = {\bf \#.CoNP}$${\bf NP} = {\bf CoNP}$

${\bf P}\not = {\bf NP}$${\bf FP} \not = {\bf \# P}$

Ker-i Ko hat gezeigt, dass es ein Orakel gibt, das PH auf der k-ten Ebene zusammenbrechen lässt. Siehe "Ker-I Ko: Relativierte Polynomzeithierarchien mit genau K-Ebenen. SIAM J. Comput. 18 (2): 392-408 (1989)".