Intuition hinter Relativierung

Question

Ich nehme den Kurs über die Computerkomplexität. Mein Problem ist, dass ich nicht verstehe Relativierungsmethode. Ich habe versucht, in vielen Lehrbüchern ein bisschen Intuition zu finden, leider ohne Erfolg. Ich werde es zu schätzen wissen, wenn jemand das Licht auf dieses Thema werfen könnte, damit ich alleine weitermachen kann. Nur wenige folgende Sätze sind Fragen und meine Gedanken zur Relativierung, sie werden helfen, die Diskussion zu steuern.

Sehr oft kommt die Relativierung im Vergleich zur Diagonalisierung, was eine Methode ist, die dazu beiträgt, zwischen zählbaren und unzähligen Satz zu unterscheiden. Es kommt irgendwie aus der Relativierung, dass $ p $ gegen $ np $ Frage nicht durch Diagonalisierung gelöst werden kann. Ich sehe die Idee nicht wirklich, warum die Relativierung die nutzlose Diagonalisierung zeigt und ob es nutzlos ist, warum tatsächlich nutzlos ist.

Die Idee hinter Oracle Turing Machine $ M^A $ ist zuerst sehr klar. Wenn es jedoch um $ np^a $ und $ p^a $ geht, verschwindet die Intuition. Oracle ist eine Blackbox, die für eine spezielle Sprache ausgelegt ist, und beantwortet die Frage, ob die Zeichenfolge für die Eingabe des Orakels in der Zeit in der Zeit 1 ist. Wie ich TM verstanden habe, das ein Orakel enthält, ist nur ein paar Hilfsvorgänge und fragen Sie das Orakel. Der Kern des TM ist also das Orakel, alles andere ist weniger wichtig. Was ist der Unterschied zwischen $ p^a $ und $ np^a $, sogar dachte, Oracle in beiden funktioniert in der Zeit 1.

Das Letzte ist das Nachweis der Existenz eines Oracle $ B $, so dass $ p^b neq np^b $. Ich fand den Beweis in mehreren Lehrbüchern und in allen scheint der Beweis sehr vage. Ich habe versucht zu benutzen "Einführung in die Komplexität" von SIPser, Kapitel9. Uneinheitlichkeit, und habe nicht die Idee, eine Liste aller Polynomzeiten zu bauen, Oracle TMS $ M_I $.

Dies ist mehr oder weniger alles, was ich über Relativierung weiß, ich werde es zu schätzen wissen, wenn einige sich entscheiden würden, seine Gedanken zu diesem Thema zu teilen.

Nachtrag: In einem der Lehrbücher fand ich ein Beispiel von $ np^b $ Sprache (Computerkomplexität: Ein moderner Ansatz von Boaz Barak Sanjeev Arora. Theorem 3.7. Seite 74). $ U_b = links {1^n: Einige Space String Space of Space Länge Space N Space ist Space in space b rechts } $ Es ist eine unäre Sprache. Ich glaube, dass (1,11.111.1111, ...) alle in $ u_b $ sind. Der Autor bestätigt, dass eine solche Sprache in $ np^b $ ist, was ich nicht verstehen kann, warum, daher kann Oracle für B alles in der Zeit auflösen. Warum brauchen wir nicht deterministisches TM mit Oracle. Wenn es kein gutes Beispiel für $ np^b $ ist, setzen Sie dies bitte so, dass Sie die Existenz von $ np^b $ genehmigen.

Answer 1

Sie haben keine Frage gestellt, aber es scheint, als ob Sie nicht wissen, was $ rm {p}^a $ bedeutet und was $ rm {np}^a $ bedeutet für eine Sprache $ a $. Die Klasse $ rm {np}^a $ ist einfach alle Sprachen, die in "NP -Zeit" enttäuscht sind, angesichts einer Turing -Maschine mit $ a $ als Orakel. Dies bedeutet eine nicht deterministische Turing-Maschine mit Zugriff auf A $ A $, die in der Polynomzeit ausgeführt wird. Das $ rm {p}^a $ ist die deterministische Version.