Spielzeugbeispiele für Barrieren gegen

Gibt es Spielzeugbeispiele, die "wesentliche" Einblicke in das Verständnis der drei bekannten Hindernisse für das $P = NP$ Problem liefern - Relativierung, natürliche Beweise und Algebrierung?

Lassen Sie mich ein Spielzeugbeispiel für die Relativierungsbarriere geben. Das kanonische Beispiel ist der Zeithierarchiesatz, dass . Der Beweis (durch Diagonalisierung) ist nur wenig komplizierter als der Beweis, dass das Halteproblem unentscheidbar ist: Wir definieren einen Algorithmus A ( x ), der den x- ten Algorithmus A x auf der Eingabe x direkt Schritt für Schritt für t simuliert ${\bf TIME}[t(n)] \subsetneq {\bf TIME}[t(n)^2]$$A(x)$$x$$A_x$$x$ Schritte und gibt dann den entgegengesetzten Wert aus. Dann argumentieren wir, dass A implementiert werden kann, um in der Zeit t ( | x | ) 2 zu laufen.$t(|x|)$$A$$t(|x|)^2$

Das Argument funktioniert genauso gut, wenn wir alle Algorithmen mit Zugriff auf eine beliebige Orakelmenge ausstatten , zu der wir in einem Berechnungsschritt Mitgliedschaftsabfragen stellen können. Eine schrittweise Simulation von A O x kann auch von A durchgeführt werden , solange A auch Zugriff auf das O-O hat . In der Notation haben wir T I M E O [ t ( n ) ] ⊊ T I M E O [ t ( n ) 2 ] für alle Orakel $O$$A_x^O$$A$$A$$O$${\bf TIME}^O[t(n)] \subsetneq {\bf TIME}^O[t(n)^2]$$O$. Mit anderen Worten, die Zeithierarchie relativiert sich .

Wir können Orakel für nichtdeterministische Maschinen auf natürliche Weise definieren, daher ist es sinnvoll, die Klassen und N P O in Bezug auf Orakel zu definieren. Aber es gibt Orakel O und O ', zu denen P O = N P O und P O ' ≠ N P O ' , so dass diese Art von direktem Simulationsargument im Zeithierarchiesatz für die Auflösung von P gegen N P nicht funktioniert$P^O$$NP^O$$O$$O'$$P^O = NP^O$$P^{O'} \neq NP^{O'}$$P$$NP$. Relativierende Argumente sind insofern mächtig, als sie weithin anwendbar sind und zu vielen großartigen Einsichten geführt haben. aber die gleiche Leistung macht sie „schwach“ in Bezug auf Fragen wie im Vergleich zu N P .$P$$NP$

Das Obige ist natürlich ein Spielzeugbeispiel - es gibt viele andere kompliziertere Beispiele für Argumente in der Komplexität, die sich noch relativieren (dh halten, wenn willkürliche Orakel eingeführt werden).