Dlaczego ten argument za

Wiem, że to głupie, ale udało mi się pomylić i potrzebuję pomocy w rozwiązaniu tego

Załóżmy, że , więc wyraźnie dla każdej wyroczni mamy co zaprzecza faktowi, że istnieje pewna wyrocznia dla której , stądA P A = N P A A P A ≠ N P A P ≠ N $P=NP$$A$$P^A=NP^A$$A$$P^A\neq NP^A$$P\neq NP$

Co jest nie tak? Dzięki!

Jasne, musisz tylko ostrożnie myśleć o tym, co to znaczy mieć wyrocznię.

Problem pochodzi z irytującego nadużycia notacji, którego używamy w CS: W stwierdzeniu , P odnosi się do zestawu języków. Ale w stwierdzeniu P A = N P A , P odnosi się do klasy maszyn Turinga (determininstic TM politytime). Powinieneś pomyśleć o tych dwóch P jako zupełnie różnych typach.$P=NP$$P$$P^A = NP^A$$P$$P$

Tak więc, nawet jeśli dwa zestawy języków i N P są takie same, deterministyczne TM polimytime wciąż nie działają w taki sam sposób jak te niedeterministyczne. W szczególności, biorąc pod uwagę wyrocznię, niedeterministyczna TM może „zadawać wiele pytań jednocześnie”, czego nie może zrobić zwykła TM. Nawet jeśli zdecydują się na ten sam zestaw języków, gdy żadnemu typowi maszyny nie zostanie udzielona dodatkowa pomoc, wyrocznia może pomóc jednemu typowi maszyny bardziej niż innemu.$P$$NP$