Folgen von

Ich habe einen Teil eines Beweises Versuch von $\oplus \mathbf{P} \subseteq \mathbf{NP}$ . Der Beweisversuch besteht aus einer Karp-Reduktion vom $\oplus \mathbf{P}$ vollständigen Problem $\oplus$ 3-REGELMÄSSIGE VERTEX-ABDECKUNG auf SAT.

Bei einem kubischen Graphen $G$ gibt die Reduktion eine CNF-Formel $F$ mit beiden folgenden Eigenschaften aus:

$F$ hat höchstens $1$ zufriedenstellende Aufgabe.
$F$ ist genau dann erfüllbar, wenn die Anzahl der Scheitelpunktabdeckungen von $G$ ungerade ist.

Fragen

Was wären die Konsequenzen von ? Eine Konsequenz , die ich schon bewusst bin , der ist folgende: zu reduzierbar wäre über zweiseitig randomisierten Reduktion. Mit anderen Worten, wir hätten (unter Verwendung des Toda-Theorems, das besagt, dass , indem lediglich durch ). Ich weiß nicht, ob $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\mathbf{PH}$ $\mathbf{NP}$ $\mathbf{PH}\subseteq\mathbf{BPP}^{\mathbf{NP}}$ $\mathbf{PH}\subseteq\mathbf{BPP}^{\oplus\mathbf{P}}$ $\oplus\mathbf{P}$ $\mathbf{NP}$ $\mathbf{BPP}^{\mathbf{NP}}$ wurde in einer bestimmten Ebene enthalten ist gezeigt werden , des Polynoms Hierarchie: wenn ja, eine weitere Folge wäre, daß auf eine solche Ebene kollabiert . ~~Darüber hinaus würde unter allgemein akzeptierten Derandomisierungsannahmen (~~ ~~) die Polynomhierarchie zwischen der ersten und der zweiten Ebene zusammenbrechen, da wir~~ ~~(mir wurde gesagt, dass dies nicht der Fall ist wahr, aber ich werde diese Zeile nicht löschen, bis ich vollständig verstanden habe, warum).~~ $i$ $\mathbf{PH}$ $i$ ~~$\mathbf{BPP} = \mathbf{P}$ $\mathbf{PH} = \mathbf{P}^\mathbf{NP} = \Delta_2^\mathbf{P}$~~

Wenn ich mich nicht irre, würde die oben erwähnte Reduktion tatsächlich mehr als beweisen . Es würde beweisen . Welche die Folgen wären , zusätzlich zu den bereits angedeutet durch ? Ich weiß nicht genau, ob die bereits überraschenden Folgen von noch überraschen würde $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{NP}$ noch in welchem Umfang. Intuitiv gehe ich davon aus, und das zu einem ziemlich großen Teil.

cc.complexity-theory graph-theory complexity-classes sat counting-complexity Giorgio Camerani
quelle

ist unter Komplement geschlossen, und die randomisierte Reduktion von PH zu

ist vielfach, daherimpliziert

tatsächlich

und

\oplus P

$\oplus\mathrm P$

\oplus P

$\oplus\mathrm P$

\oplus P \subseteq N P

$\oplus\mathrm P\subseteq\mathrm{NP}$

P H = Σ_{2}^{P} = Π_{2}^{P} = A M \cap c o A M

$\mathrm{PH}=\Sigma^P_2=\Pi^P_2=\mathrm{AM}\cap\mathrm{coAM}$

P H \subseteq N P / p o l y \cap c o N P / p o l y

$\mathrm{PH}\subseteq\mathrm{NP/poly}\cap\mathrm{coNP/poly}$ . UP macht keinen großen Unterschied (vgl. Das Fehlen von nützlichen Informationen in cstheory.stackexchange.com/questions/3887 ).

Emil Jeřábek

@ EmilJeřábek Danke für deinen interessanten Kommentar, ich wusste diese Konsequenzen nicht. Ich kannte die Frage, auf die Sie mich hingewiesen haben, aber ich hätte erwartet, dass

(sowie

) überraschend ist, zumindest weil nicht bekannt ist, dass

vollständige Probleme hat. Es ist interessant, wie etwas, von dem allgemein angenommen wird, dass es falsch ist (

), keine schockierende Konsequenz hat, wenn es wahr ist. Sie könnten erwägen, Ihren Kommentar in eine Antwort zu erweitern ...

\oplus P \subseteq U P

$\oplus \mathbf{P}\subseteq\mathbf{UP}$

N P \subseteq U P

$\mathbf{NP}\subseteq\mathbf{UP}$

U P

$\mathbf{UP}$

N P \subseteq U P

$\mathbf{NP}\subseteq\mathbf{UP}$

Giorgio Camerani

Nein, du liegst völlig falsch. BPP = P sagt nur, dass jede Sprache, die von einer BPP-Maschine berechnet werden kann, auch von einer P-Maschine berechnet werden kann. Es sagt überhaupt nichts über Sprachen aus, die von einer BPP-Maschine mit einem nicht trivialen Orakel berechnet werden können. Durch Ihr fehlerhaftes Argument impliziert NP = P

für jedes

, von dem wir wissen, dass es falsch ist, daher ist

gelöst. Und im Übrigen würde Ihr Argument

implizieren , da es Orakel

für die

{N P}^{A} = P^{A}

$\mathrm{NP}^A=\mathrm P^A$

A

$A$

N P \neq P

$\mathrm{NP}\ne\mathrm P$

B P P \neq P

$\mathrm{BPP}\ne\mathrm P$

A

$A$

{B P P}^{A} \neq P^{A}

$\mathrm{BPP}^A\ne\mathrm P^A$ .

Emil Jeřábek

@Giorgio: Er behauptet nur, dass die Argumentation, die Sie in Betracht gezogen haben, unter diesen Umständen nicht funktioniert. Relevanter Teil: "Wenn die Maschine, an die ich das Orakel anbringe, mindestens genauso leistungsfähig ist, warum sollte die Aufnahme nicht folgen?" Er scheint nicht zu sagen, dass die Behauptung selbst falsch ist; nur dass deine spezielle Intuition nicht funktioniert. Wir können noch nicht ausschließen, dass probabilistische Aspekte des PPTM nicht mehr von diesem Orakel profitieren könnten. Das probabilistische TM verfügt über mehr Werkzeuge, aber ohne zusätzliche Werkzeuge (wie das NP-Orakel) bietet das Werkzeug möglicherweise keinen strengen Nutzen.

mdxn

Selbst mit der Annahme, dass ein PRNG existiert, das stark genug ist, um P und BPP zu kollabieren, verstehe ich nicht, warum dies notwendigerweise bedeuten muss, dass BPP mit einem NP-Orakel und P mit einem NP-Orakel dasselbe sein müssen. Normalerweise haben PRNGs die Garantie, dass keine Polysize-Schaltung ihre Ausgabe von wirklich zufälligen Bits unterscheiden kann. Aber für die Orakelmaschinen benötigen Sie die Garantie für jede Polysize-Schaltung mit zulässigen NP-Gates, und diese ist stärker. Impagliazzo-Wigderson relativiert zwar, aber Sie müssen die Annahme der Härte verstärken ( eccc.hpi-web.de/report/1998/055/comment/1/download )

Sasho Nikolov

Folgen von

Antworten: