как оракул

Имеет ли $\mathsf{NP^{NP \,\cap\, coNP}=NP}$удерживать?

Ясно, что $\mathsf{NP^{NP}\neq NP}$ , но мне кажется, что $\mathsf{NP\cap coNP}$ является «детерминированным», что заставляет меня верить, что это правда.

Есть ли простое доказательство (или, может быть, просто по определению)?

Да. Действительно, оракул удовлетворяет условию Н Р А = Н P тогда и только тогда , когда A ∈ N P П с õ N P . Этот класс называется L o w ( N P ) или иногда L 1 P (см. Ссылку и цитируемую там статью для более подробного объяснения низкой иерархии в целом).$A$$\mathsf{NP}^A=\mathsf{NP}$$A \in \mathsf{NP} \cap \mathsf{coNP}$$\mathsf{Low(NP)}$$\mathsf{L_1 P}$

Ваша интуиция о «детерминизме» на самом деле несколько верна (хотя она не является достаточно детерминированной, чтобы мы могли сделать вывод, что ). Попробуйте выполнить это упражнение , и вы увидите , что это интуиция доказанной: первое шоу - тщательно, изложив деталь - что если ∈ P , то N P = N P . Выясните, какая именно часть вашего доказательства не работает, если вы только предполагаете, что A ∈ N P , а затем понимаете, почему эта часть работает, когда A ∈ 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}$

(Показывать обратное тоже не сложно: означает A ∈ N P ∩ c o N P. )$\mathsf{NP}^A = \mathsf{NP}$$A \in \mathsf{NP} \cap \mathsf{coNP}$