Przykłady zabawek dla barier dla

Czy są jakieś przykłady zabawek, które zapewniają „niezbędny” wgląd w trzy znane bariery dla problemu - relatywizacja, dowody naturalne i algebryzacja?$P = NP$

Pozwól, że podam zabawkowy przykład bariery relatywizacji. Przykładem kanonicznym jest twierdzenie o hierarchii czasu, że . Dowód (diagonalizacja) jest tylko trochę bardziej zaangażowany niż dowód, że problem zatrzymania jest nierozstrzygalny: definiujemy algorytm A (x), który symuluje x algorytm A_x na wejściu x bezpośrednio krok po kroku dla t (| x |) kroki, a następnie wyświetla przeciwną wartość. Następnie argumentujemy, że A można zaimplementować, aby działało w czasie t (| x |) ^ 2 .${\bf TIME}[t(n)] \subsetneq {\bf TIME}[t(n)^2]$$A(x)$$x$$A_x$$x$$t(|x|)$$A$$t(|x|)^2$

Argument działa równie dobrze, jeśli wyposażymy wszystkie algorytmy w dostęp do dowolnego zestawu wyroczni $O$ , do którego zakładamy, że możemy zadawać pytania członkostwa w jednym kroku obliczeniowym. Krok po kroku przez symulację $A_x^O$ może być również przeprowadzone przez $A$ , tak długo jak dostęp wyroczni O też. W notacji mamy {\ bf godzinę,} ^ O [T (n)] \ subsetneq {\ CZAS BF} ^ O [T (N ^ 2)] dla wszystkich Oracles O . Innymi słowy, hierarchia czasu relatywizuje się .$A$$O$${\bf TIME}^O[t(n)] \subsetneq {\bf TIME}^O[t(n)^2]$$O$

Możemy zdefiniować wyrocznie dla niedeterministycznych maszyn w naturalny sposób, więc sensowne jest zdefiniowanie klas $P^O$ i $NP^O$ w odniesieniu do wyroczni. Istnieją jednak wyrocznie $O$ i $O'$ stosunku do których $P^O = NP^O$ i $P^{O'} \neq NP^{O'}$ , więc ten rodzaj argumentu bezpośredniej symulacji w twierdzeniu o hierarchii czasu nie zadziała do rozwiązania $P$ porównaniu z $NP$ . Argumenty relatywizujące są potężne, ponieważ mają szerokie zastosowanie i doprowadziły do ​​wielu świetnych spostrzeżeń; ale ta sama moc czyni je „słabymi” w odniesieniu do pytań takich jak $P$ kontra $NP$ .

Powyżej jest oczywiście przykład zabawki - istnieje wiele innych bardziej skomplikowanych przykładów złożonych argumentów, które wciąż się relatywizują (tj. Wstrzymują się, gdy wprowadzane są arbitralne wyroki).