Pourquoi cet argument pour faux?

Je sais que c'est idiot, mais j'ai réussi à me confondre et j'ai besoin d'aide pour régler ça

Supposons que , alors clairement pour chaque oracle nous avons qui contredit le fait qu'il existe un oracle pour lequel , d'où$P=NP$$A$$P^A=NP^A$$A$$P^A\neq NP^A$$P\neq NP$

Qu'est-ce qui ne va pas? Merci!

Bien sûr, il vous suffit de bien réfléchir à ce que signifie avoir un oracle.

Le problème vient d'un abus de notation ennuyeux que nous utilisons dans CS: Dans l'instruction , réfère à un ensemble de langages. Mais dans l'énoncé , réfère à une classe de machines de Turing (MT polytemporaires déterministes). Vous devriez considérer ces deux comme des types complètement différents.$P=NP$$P$$P^A = NP^A$$P$$P$

Ainsi, même si les deux ensembles de langages et sont les mêmes, les MT polytemporaires déterministes ne fonctionnent toujours pas de la même manière que les MT non déterministes. En particulier, étant donné un oracle, une MT non déterministe peut "poser plusieurs questions à la fois", ce que la MT régulière ne peut pas faire. Ainsi, même s'ils décident du même ensemble de langues lorsqu'aucun type de machine ne reçoit d'aide supplémentaire, l'oracle peut aider un type de machine plus qu'un autre.$P$$NP$