comme oracle

D'abord, oui. En effet, un oracle $A$ satisfait $\mathsf{NP}^{A} = \mathsf{NP}$ si et seulement si $A \in \mathsf{NP} \cap \mathsf{coNP}$ . Cette classe est appelée $\mathsf{Low(NP)}$ ou parfois $\mathsf{L_1 P}$ : complexitézoo.uwaterloo.ca / Complexity_Zoo : L # lkp . Deuxièmement, je ne pense pas qu'il soit clair du tout que $\mathsf{NP}^{\mathsf{NP}} \neq \mathsf{NP}$ , bien qu'il s'agisse d'une croyance largement répandue. En particulier, cela implique $\mathsf{P} \neq \mathsf{NP}$ et semble être strictement plus fort, car il n'y a aucune implication relativisable dans l'autre sens.

De plus, les gens qui croient que la FACTORISATION est difficile peuvent contester votre intuition selon laquelle $\mathsf{NP \cap coNP}$ est «déterministe».

@JoshuaGrochow: Je pense que vous devriez ajouter cela comme réponse, avec quelques explications sur ce que sont les classes dans la basse hiérarchie; c'est à peu près une aussi bonne réponse que le PO est susceptible d'obtenir.

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

@NieldeBeaudrap: Mon hésitation à l'afficher comme réponse plutôt que comme commentaire était que, bien que je pense que maomao a véritablement posé cette question sérieusement, elle peut être, et a été dans le passé, donnée comme exercice de devoirs.