Dlaczego relatywizacja jest barierą?

Kiedy wyjaśniłem dowód Baker-Gill-Solovay, że istnieje wyrocznia, którą możemy mieć, , oraz wyrocznia, z którą możemy otrzymać P ≠ N P przyjacielowi, pojawiło się pytanie, dlaczego takie techniki nie nadają się do udowodnienia problemu P ≠ N P i nie mogłem udzielić zadowalającej odpowiedzi.$\mathsf{P} = \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Mówiąc bardziej konkretnie, jeśli mam podejście do udowodnienia i gdybym mógł zbudować wyrocznie, aby sytuacja taka jak wyżej się wydarzyła, dlaczego powoduje to, że moja metoda jest nieważna?$\mathsf{P} \neq \mathsf{NP}$

Wszelkie ekspozycje / przemyślenia na ten temat?

Mówiąc bardziej konkretnie, jeśli mam podejście do udowodnienia P ≠ NP i gdybym mógł zbudować wyrocznie, aby sytuacja taka jak wyżej się wydarzyła, dlaczego powoduje to, że moja metoda jest nieważna?

Zauważ, że to ostatnie „jeśli” nie jest warunkiem, ponieważ Baker, Gill i Solovay już zbudowali taką wyrocznię. Jest tylko matematyczną prawdą, że (1) istnieje wyrocznia, względem której P = NP, i że (2) istnieje wyrocznia, względem której P ≠ NP.

Oznacza to, że jeśli masz podejście do udowodnienia P ≠ NP, a ten sam dowód potwierdzi równie silniejszy wynik „P ^A ≠ NP ^A dla wszystkich wyroczni A ”, wówczas twoje podejście jest skazane na porażkę, ponieważ byłoby to sprzeczne (1).

Innymi słowy, istnieje pewna fundamentalna różnica między udowodnieniem P ≠ NP a udowodnieniem np. Twierdzenia o hierarchii czasowej, ponieważ dowód tego ostatniego wykorzystuje po przekątnej i ma jednakowe zastosowanie do każdego relatywizowanego świata.

Oczywiście nie oznacza to, że nie ma dowodów na P ≠ NP. Taki dowód (jeśli taki istnieje) musi nie udowadniać silniejszego wyniku wspomnianego powyżej. Innymi słowy, pewna część dowodu musi odróżniać świat nierelatywizujący od światów relatywizowanych arbitralnie.

Są już dobre odpowiedzi, ale chciałbym dodać kilka małych punktów.

Załóżmy, że mamy technikę rozwiązywania problemów, np . Diagonalizację . Załóżmy, że chcemy pokazać, że technika nie może rozwiązać problemu specyficznego np vs. N $\mathsf{P}$$\mathsf{NP}$ . Jak to pokazać?

Zanim przejdziemy dalej, zauważ, że technika taka jak diagonalizacja nie jest tutaj formalną koncepcją (chociaż możemy to zrobić). Ponadto fakt, że technika sama w sobie nie jest w stanie rozwiązać problemu, nie oznacza, że ​​w ogóle nie jest przydatny w rozwiązywaniu problemu, możemy go zmodyfikować i / lub połączyć z innymi technikami w celu rozwiązania problemu.

Wróćmy teraz do pytania. Jednym ze sposobów wykazania, że ​​technika nie może rozwiązać konkretnego problemu, jest wykazanie, że gdyby mogła, działałaby również w innych ramach rozwiązywania innego pytania, a odpowiedź, którą otrzymalibyśmy w tym przypadku, byłaby błędna. Oto co się tutaj dzieje. Jeżeli diagonalizacja może oddzielić z P, wtedy sam argument może być wykorzystywana do oddzielania N P A z P A dla wszystkich A . Ale wiemy, że nie jest wyrocznią, tak że to jest fałszywe (podejmować żadnych P S p c e -Complete problemem jak wyroczni). Zatem diagonalizacja nie może oddzielić $\mathsf{NP}$$\mathsf{P}$$\mathsf{NP^A}$$\mathsf{P^A}$$A$$\mathsf{PSpace}$ od P .$\mathsf{NP}$$\mathsf{P}$

Zasadniczym punktem tego argumentu jest rodzaj zasady przeniesienia :

możemy przenieść argument diagonalizacji dla baz TM bez Oracle do baz TM z Oracle.

Jest to możliwe tutaj, ponieważ argumenty diagonalizacji oparte są na symulacji maszyn, ponadto symulacja nie zależy od wewnętrznych maszyn, ale tylko od ostatecznych odpowiedzi z tych symulacji. Ten rodzaj diagonalizacji nazywany jest prostą diagonalizacją . W symulacji nie ma znaczenia, jak działa maszyna, zależy nam tylko na ostatecznej odpowiedzi maszyny. Dodanie wyroczni nie zmieni tego, więc symulacja i argument będą działać również w ramach, w których mamy wyrocznie.

$\mathsf{P}$$SAT$$SAT$

$\mathsf{NP}$$\mathsf{P}$

$\mathsf{P}$$\mathsf{NP}$

$M$$M$$M$$M$być tą instancją. To jest widok dużego obrazu, jeśli chcesz zobaczyć szczegóły, sprawdź artykuł Kozen.

Letni:

• $\mathsf{P}$$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$
• $\mathsf{NP}$$\mathsf{P}$
• Powodem tego przeniesienia z frameworka bez wyrocznika do frameworka z wyroczniami jest to, że prosta diagonalizacja opiera się na symulacji czarnych skrzynek baz TM i nie ma znaczenia, jak działają maszyny, czy ma wyrocznię, czy nie.

Dwa dobre artykuły, aby dowiedzieć się więcej o diagonalizacji

• Artykuł sondażowy Lance Fortnow „Diagonalizacja”, 2001 i
• Artykuł Russella Impagliazza, Valentine Kabanets i Antoniny Kolokołowej „Podejście aksjomatyczne do algebrizacji”, 2009. (Należy zauważyć, że algebraizacja jest przedłużeniem prostej diagonalizacji ).

$\mathrm{A}$$\mathrm{B}$$\mathrm{A} \neq \mathrm{B}$$\mathrm{A} = \mathrm{B}$$\mathrm{O}$$\mathrm{A}^\mathrm{O} \neq \mathrm{B}^\mathrm{O}$$\mathrm{A}^\mathrm{O} = \mathrm{B}^\mathrm{O}$$P = NP$$P \neq NP$

Dlaczego to jest problem? Kiedy pojawił się ten dowód, większość technik i sztuczek, które znaliśmy, aby oddzielić lub zawalić klasy złożoności, „relatywizować”, ponieważ działają one w odniesieniu do każdej wyroczni. Na przykład, twierdzenie o hierarchii czasu (a także jego przestrzeń i niedeterministyczne wersje) „relatywizuje”: dowodzą one separacji dla klas, dla których separacja relatywizuje, i w rzeczywistości dowodzą silniejszego wyniku, jaki separacja ma w odniesieniu do każda wyrocznia.

$P = NP$$P \neq NP$$P \neq NP$$\mathrm{PSPACE}$