Ist

Ist mit Orakelzugang zu N P größer als nur N P ? Soweit ich weiß, ist N P N P nur eine Turingmaschine, die Abfragen an eine andere N P- Maschine stellen kann, wenn dies der Fall ist, als N P N P N P simulieren kann . Stimmt etwas mit diesem Argument nicht?$NP$$NP$$NP$$NP^ {NP}$$NP$$NP$$NP^{NP}$

Um meine Kommentare als Antwort neu zu formulieren und ein wenig zu erweitern:

Wir wissen nicht, ob NP ^NP  =  NP ist - es ist ein notorisch offenes Problem in der Komplexitätstheorie, obwohl wir wie bei P gegen NP vermuten, dass sie nicht gleich sind. Einer der Gründe, warum wir nicht wissen, wie man ein NP- Orakel mit einer NP- Maschine simuliert, ist, dass wir nicht wissen, wie die NP- Maschine "keine" Fälle von Problemen erkennen kann, die an das Orakel gesendet wurden.

Die Klasse NP ^NP ist auch als und gehört zu den Klassen auf der zweiten Ebene der Polynomhierarchie . Die anderen Klassen auf der zweiten Ebene sind Δ P $\Sigma_2^P$ (Alle diese Klassen wären gleich, wenn wir eincoNP-Orakelverwendenwürden. Der einzige Unterschied besteht im Wesentlichen in einer logischen Negation der Ausgabe.) Die Klassen der dritten und höheren Hierarchieebene werden definiert, indem ihnen noch weitereNP-Orakel gegeben werden: Δ P k +

$$\begin{align*} \Delta_2^P &:= \mathsf{P}^{\mathsf{NP}}, \\ \Pi_2^P &:= \mathsf{coNP}^{\mathsf{NP}}. \end{align*}$$ Wiederum ist der Unterschied zwischen denOrakelnΣPkundΠPkim Wesentlichen die Negation seiner Ausgabe. Wir definieren auchΔP0=ΣP0=ΠP0=P; Anhand der obigen Definition können Sie sehen, dass diesΔP1:=P,  ΣP1:=NPundΠP1:=coergibt $$\begin{align*} \Delta_{k+1}^P &:= \mathsf{P}^{\,\Sigma_{k}^P} = \mathsf{P}^{\,\Pi_k^P}, \\[1ex] \Sigma_{k+1}^P &:= \mathsf{NP}^{\,\Sigma_{k}^P} = \mathsf{NP}^{\,\Pi_k^P}, \\[1ex] \Pi_{k+1}^P &:= \mathsf{coNP}^{\,\Sigma_{k}^P} = \mathsf{coNP}^{\,\Pi_k^P}. \\\end{align*}$$ $\Sigma_k^P$$\Pi_k^P$$\Delta_0^P = \Sigma_0^P = \Pi_0^P = \mathsf{P}$$\Delta_1^P := \mathsf{P}$$\Sigma_1^P := \mathsf{NP}$ .$\Pi_1^P := \mathsf{coNP}$

Es wird angenommen, dass die verschiedenen Klassen der Polynomhierarchie unterschiedlich sind; Unabhängig davon, wie viele Schichten von NP- Orakeln Sie bereitstellen, wird nicht angenommen, dass sich die Rechenleistung zu irgendeinem Zeitpunkt stabilisiert. Wenn NP ^NP  =  NP , dann kollabiert die Polynomhierarchie auf ihre erste Ebene : Alle -Klassen für k  ≥ 1 wären gleich NP (ebenso wie alle Π P k -Klassen einschließlich coNP) . als NP- Maschine könnte jedes Problem in Π P k lösen$\Sigma_k^P$$\Pi_k^P$$\Pi_k^P$durch Simulation eines Turms von NP- Orakeln).

ist als zweite Ebene derPolynomhierarchie bekannt.$\mathsf{NP}^{\mathsf{NP}}$

$\mathsf{NP}^{\mathsf{NP}} \supseteq \mathsf{coNP}$$\mathsf{NP} \supseteq \mathsf{coNP}$