als Orakel

Tut $\mathsf{NP^{NP \,\cap\, coNP}=NP}$halten?

Klar $\mathsf{NP^{NP}\neq NP}$ , aber es scheint mir, dass $\mathsf{NP\cap coNP}$ "deterministisch" ist, was mich glauben lässt, dass dies wahr ist.

Gibt es einen einfachen Beweis (oder vielleicht nur per Definition)?

Ja. In der Tat erfüllt ein Orakel genau dann N P A = N P, wenn A ≤ N P ≤ c o N P ist . Diese Klasse wird L o w ( N P ) oder manchmal L 1 P genannt (siehe den Link und das dort zitierte Papier für eine genauere Erklärung der niedrigen Hierarchie im Allgemeinen).$A$$\mathsf{NP}^A=\mathsf{NP}$$A \in \mathsf{NP} \cap \mathsf{coNP}$$\mathsf{Low(NP)}$$\mathsf{L_1 P}$

Ihre Intuition über "Determinismus" ist tatsächlich etwas richtig (obwohl sie nicht deterministisch genug ist, um zu folgern, dass ). Versuchen Sie dies als eine Übung , und Sie werden diese Intuition sehen rehabilitiert: erste Show - sorgfältig, um die Details Buchstabieren - , dass , wenn A ∈ P , dann N P A = N P . Finden Sie genau den Teil Ihres Beweises heraus, der nicht funktioniert, wenn Sie nur A ∈ N P annehmen , und stellen Sie dann fest, warum dieser Teil funktioniert, wenn A ∈ N $\mathsf{P} = \mathsf{NP} \cap \mathsf{coNP}$$A \in \mathsf{P}$$\mathsf{NP}^{A} = \mathsf{NP}$$A \in \mathsf{NP}$ .$A \in \mathsf{NP} \cap \mathsf{coNP}$

(Das Gegenteil zu zeigen ist auch nicht allzu schwierig: impliziert A ∈ N P ∩ c o N P. )$\mathsf{NP}^A = \mathsf{NP}$$A \in \mathsf{NP} \cap \mathsf{coNP}$