sebagai oracle

Pertama, ya. Memang, sebuah oracle memenuhi N P A = N P jika dan hanya jika A ∈ N P ∩ c o N P . Kelas ini disebut L o w ( N P ) atau kadang-kadang L 1 P : kompleksitaszoo.uwaterloo.ca/Complexity_Zoo:L#lkp . Kedua, saya kira sama sekali tidak jelas bahwa N P N P ≠ N P , meskipun ini adalah kepercayaan yang dipegang secara luas. Secara khusus, ini menyiratkan $A$$\mathsf{NP}^{A} = \mathsf{NP}$$A \in \mathsf{NP} \cap \mathsf{coNP}$$\mathsf{Low(NP)}$$\mathsf{L_1 P}$$\mathsf{NP}^{\mathsf{NP}} \neq \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$ dan tampaknya benar-benar lebih kuat, karena tidak ada implikasi relativizable sebaliknya.

Juga, orang-orang yang percaya bahwa FAKTOR itu sulit dapat mengambil masalah dengan intuisi Anda bahwa $\mathsf{NP \cap coNP}$ adalah "deterministik".

@ JoshuaGrochow: Saya pikir Anda harus menambahkan itu sebagai jawaban, dengan beberapa penjelasan tentang apa kelas-kelas dalam hirarki rendah itu; ini tentang jawaban yang sama baiknya dengan yang OP dapatkan.

$NP^{NP}$$co-NP$$NP$

@NieldeBeaudrap: Keragu-raguan saya untuk mempostingnya sebagai jawaban daripada komentar adalah bahwa, meskipun saya percaya maomao benar-benar mengajukan pertanyaan ini dengan sungguh-sungguh, itu bisa saja, dan telah di masa lalu, diberikan sebagai latihan pekerjaan rumah.