jako wyrocznia

Czy $\mathsf{NP^{NP \,\cap\, coNP}=NP}$trzymać?

Najwyraźniej $\mathsf{NP^{NP}\neq NP}$ , ale wydaje mi się, że $\mathsf{NP\cap coNP}$ jest „deterministyczna”, co pozwala mi wierzyć, że to prawda.

Czy istnieje prosty dowód (a może tylko z definicji)?

Tak. Rzeczywiście, oracle spełnia N P A = N P , wtedy i tylko wtedy, gdy A ∈ N P ∩ c o N P . Ta klasa nazywa się L o w ( N P ) lub czasami L 1 P (patrz link i cytowany tam dokument, aby uzyskać ogólne wyjaśnienie niskiej hierarchii w ogóle).$A$$\mathsf{NP}^A=\mathsf{NP}$$A \in \mathsf{NP} \cap \mathsf{coNP}$$\mathsf{Low(NP)}$$\mathsf{L_1 P}$

Twoja intuicja dotycząca „determinizmu” jest w rzeczywistości nieco poprawna (chociaż nie jest wystarczająco deterministyczna, abyśmy mogli dojść do wniosku, że ). Spróbuj to jako ćwiczenie, a zobaczysz to intuicja zrehabilitowany: pierwszy koncert - ostrożnie, literowania szczegóły - że jeśli ∈ P , a następnie N P = N P . Dowiedzieć się dokładnie taką część swojego dowodu, że nie działa, jeśli tylko założyć, A ∈ N P , a następnie zrozumieć, dlaczego ta część działa gdy ∈ N P ∩ C $\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}$

(Pokazanie odwrotności też nie jest zbyt trudne: oznacza A ∈ N P ∩ c o N P. )$\mathsf{NP}^A = \mathsf{NP}$$A \in \mathsf{NP} \cap \mathsf{coNP}$