como oráculo

Primeiro sim. Com efeito, um Oracle $A$ satisfaz $\mathsf{NP}^{A} = \mathsf{NP}$ se e apenas se $A \in \mathsf{NP} \cap \mathsf{coNP}$ . Esta classe é chamado $\mathsf{Low(NP)}$ ou, por vezes, $\mathsf{L_1 P}$ : complexityzoo.uwaterloo.ca/Complexity_Zoo:L#lkp . Segundo, não acho que fique claro que $\mathsf{NP}^{\mathsf{NP}} \neq \mathsf{NP}$ , embora essa seja uma crença amplamente aceita. Em particular, implica $\mathsf{P} \neq \mathsf{NP}$ e parece ser estritamente mais forte, pois não há implicações relativizáveis ​​pelo contrário.

Além disso, as pessoas que acreditam que FACTORING é difícil podem ter problemas com a sua intuição de que $\mathsf{NP \cap coNP}$ é "determinista".

@ JoshuaGrochow: Eu acho que você deve adicionar isso como resposta, com alguma exposição sobre o que são as classes na hierarquia baixa; é uma resposta tão boa quanto o OP provavelmente obterá.

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

@NieldeBeaudrap: Minha hesitação em publicá-la como uma resposta, em vez de comentar, foi que, embora eu acredite que o maomao genuinamente fez essa pergunta a sério, ela pode ser e foi no passado, dada como um exercício de lição de casa.