Oracle machine

Black Box -Systeme
Black Box -Systeme
System
	Flugschreiber · Oracle Machine
Methoden und Techniken
	Black-Box-Tests · Blackboxing
Verwandte Techniken
	Nach vorne füttern · Verschleierung · Mustererkennung · weiße Kiste · White-Box-Test · Systemidentifikation
Grundlagen
	A priori Information · Kontroll systeme · Offene Systeme · Unternehmensforschung · Thermodynamische Systeme

Im Komplexitätstheorie und Computerbarkeitstheorie, ein Oracle Machine ist ein abstrakte Maschine verwendet zum Studium Entscheidungsprobleme. Es kann als visualisiert werden Turing Maschine mit einer Flugschreiber, genannt Orakel, was in der Lage ist, bestimmte Probleme in einem einzigen Betrieb zu lösen. Das Problem kann von jedem sein Komplexitätsklasse. Eben unentscheidbare Probleme, so wie die Problem stoppen, kann verwendet werden.

Orakel

Eine Orakelmaschine kann als als konzipiert werden Turing Maschine mit einem verbunden Orakel. Das Orakel ist in diesem Zusammenhang eine Entität, die in der Lage ist, ein Problem zu lösen, was zum Beispiel a sein kann Entscheidungsproblem oder ein Funktionsproblem. Das Problem muss nicht berechnet werden; Es wird nicht angenommen, dass das Orakel ein Turing -Maschine oder ein Computerprogramm ist. Das Orakel ist einfach ein "Flugschreiber"Das ist in der Lage, eine Lösung für jede Instanz eines bestimmten Rechenproblems zu erzeugen:

Ein Entscheidungsproblem wird als Set dargestellt A von natürlichen Zahlen (oder Saiten). Eine Instanz des Problems ist eine willkürliche natürliche Zahl (oder Zeichenfolge). Die Lösung für die Instanz lautet "Ja", wenn sich die Nummer (Zeichenfolge) im Satz befindet, und sonst "Nein".
Ein Funktionsproblem wird durch eine Funktion dargestellt f von natürlichen Zahlen (oder Saiten) bis hin zu natürlichen Zahlen (oder Saiten). Eine Instanz des Problems ist eine Eingabe x zum f. Die Lösung ist der Wert f(x).

Eine Oracle -Maschine kann alle üblichen Vorgänge einer Turing -Maschine ausführen und auch das Orakel abfragen, um eine Lösung für eine beliebige Instanz des Rechenproblems für dieses Orakel zu erhalten. Wenn das Problem beispielsweise ein Entscheidungsproblem für einen Satz ist A Die Oracle -Maschine liefert das Orakel mit einer natürlichen Zahl, und das Orakel antwortet mit "Ja" oder "Nein", die angibt, ob diese Zahl ein Element von ist A.

Definitionen

Es gibt viele äquivalente Definitionen von Oracle Turing -Maschinen, wie unten erläutert. Der hier präsentierte Van Melkebeek (2000: 43).

Eine Oracle -Maschine wie eine Turing -Maschine beinhaltet:

a Arbeitsband: Eine Sequenz von Zellen ohne Beginn oder Ende, von denen jeder ein B (für Blank) oder ein Symbol aus dem Bandalphabet enthalten kann;
a Kopf lesen/schreiben, die sich auf einer einzelnen Zelle des Arbeitsbands beruht und die Daten dort lesen, neue Daten schreiben und seine Position entlang des Bandes erhöhen oder verringern;
a Kontrollmechanismus, was in einer endlichen Anzahl von sein kann Zuständeund die unterschiedliche Aktionen (Lesen von Daten, Schreiben von Daten, Verschieben des Kontrollmechanismus und Änderungszustände) abhängig von dem aktuellen Zustand und den gelesenen Daten ausführen.

Zusätzlich zu diesen Komponenten enthält eine Oracle -Maschine auch:

ein Oracle Tape, das ist ein halbgebundenes Band, das vom Arbeitsband getrennt ist. Das Alphabet für das Oracle -Band kann sich vom Alphabet für das Arbeitsband unterscheiden.
ein Oracle Head was wie der Lese-/Schreibkopf nach links oder rechts entlang der Oracle -Bandles- und Schreibsymbole bewegen kann;
Zwei besondere Staaten: Der Ask State und der Antwortstatus.

Von Zeit zu Zeit kann die Oracle -Maschine in den Ask -Status eintreten. In diesem Fall werden die folgenden Aktionen in einem einzigen rechnerischen Schritt ausgeführt:

Der Inhalt des Orakelbandes wird als Instanz des Rechenproblems des Orakels angesehen.
Das Orakel wird konsultiert und der Inhalt des Orakelbandes wird durch die Lösung für die Instanz des Problems ersetzt.
Der Oracle -Kopf wird auf das erste Quadrat auf dem Oracle Tape bewegt.
Der Zustand der Oracle -Maschine wird in die Antwort geändert.

Der Effekt des Wechsels in den Ask -Status besteht daher darin, in einem einzigen Schritt eine Lösung für die Probleminstanz zu empfangen, die auf dem Oracle Tape geschrieben ist.

Alternative Definitionen

Es gibt viele alternative Definitionen für die oben dargestellten. Viele davon sind auf den Fall spezialisiert, in dem das Oracle ein Entscheidungsproblem löst. In diesem Fall:

Einige Definitionen haben anstatt die Antwort auf das Oracle Tape zu schreiben, und haben zusätzlich zum Ask -Status zwei spezielle Zustände mit Ja und Nein. Wenn das Orakel konsultiert wird, wird der nächste Zustand als Ja ausgewählt, wenn der Inhalt des Oracle -Bandes im Oracle -Set liegt, und an das Nein ausgewählt, wenn der Inhalt nicht im Oracle -Set liegt (Adachi 1990: 111).
Einige Definitionen vermeiden das separate Orakelband. Wenn der Oracle -Status eingegeben wird, wird ein Bandsymbol angegeben. Das Orakel wird von der Häufigkeit gefragt, in der dieses Bandsymbol auf dem Arbeitsband angezeigt wird. Wenn sich diese Zahl im Oracle -Set befindet, ist der nächste Zustand der Ja -Zustand; Wenn dies nicht der Fall ist, ist der nächste Staat der NO -Staat (Rogers 1967: 129).
Eine andere alternative Definition macht das Oracle Tape nur schreibgeschützt und beseitigt die Anfrag- und Antwortzustände vollständig. Bevor die Maschine gestartet wird, die Indikatorfunktion des Oracle -Sets wird auf dem Oracle -Band unter Verwendung der Symbole 0 und 1 geschrieben. Die Maschine kann dann das Oracle abfragen, indem Sie auf das richtige Quadrat auf dem Oracle -Band scannen und den dort befindlichen Wert lesen (Soare 1987: 47, Rogers 1967: 130).

Diese Definitionen sind aus Sicht der Turing-Berechnung äquivalent: Eine Funktion ist von einem bestimmten Orakel unter all diesen Definitionen ausgestattet, wenn sie unter einem von ihnen oraklerisch ist. Die Definitionen sind jedoch aus Sicht der Rechenkomplexität nicht äquivalent. Eine Definition wie die von Van Melkebeek mit einem Orakelband, das möglicherweise ein eigenes Alphabet hat, ist im Allgemeinen erforderlich.

Komplexitätsklassen von Orakelmaschinen

Das Komplexitätsklasse von Entscheidungsprobleme Lösbar durch einen Algorithmus in Klasse A mit einem Orakel für eine Sprache L wird als a genannt^L. Zum Beispiel p^Sa ist die Klasse von Problemen lösbar in Polynomzeit durch eine deterministische Turing -Maschine mit einem Orakel für die Boolesche Zufriedenheitsproblem. Die Notation a^B kann auf eine Reihe von Sprachen B (oder eine Komplexitätsklasse B) durch die folgende Definition erweitert werden:

{\ displaystyle a^{b} = \ bigcup _ {l \ in b} a^{l}}

Wenn eine Sprache l ist Komplett für einige Klasse B, dann a^L= A^B vorausgesetzt, Maschinen in einem können Reduktionen ausführen, die in der Vollständigkeitsdefinition von Klasse B. verwendet werden, da SAT ist NP-Complete in Bezug auf die Polynomzeitverkleinerung, p^Sa= P^Np. Aber wenn a = Dlogime, dann ein^Sa darf nicht gleich a gleich sind^Np. (Beachten Sie, dass die Definition von ${\ displayStyle a^{b}}$ oben angegeben ist nicht vollständig Standard. In einigen Kontexten, wie dem Beweis der Zeit und Raumhierarchie TheoremsEs ist nützlicher anzunehmen, dass die abstrakte Maschine die Klasse definiert ${\ displayStyle a}$ Hat nur Zugriff auf ein einzelnes Orakel für eine Sprache. In diesem Zusammenhang, ${\ displayStyle a^{b}}$ ist nicht definiert, wenn die Komplexitätsklasse ${\ displayStyle B}$ hat keine vollständigen Probleme in Bezug auf die zur Verfügung stehenden Reduzierungen, die zur Verfügung stehen ${\ displayStyle a}$ .))

Es versteht sich, dass NP ⊆ P.^Np, aber die Frage, ob NP^Np, P^Np, NP und P sind bestenfalls vorläufig. Es wird angenommen, dass sie unterschiedlich sind, und dies führt zur Definition der Polynomhierarchie.

Oracle -Maschinen sind nützlich, um die Beziehung zwischen zu untersuchen Komplexitätsklassen P und NP, unter Berücksichtigung der Beziehung zwischen p^A und np^A Insbesondere für ein Orakel A wurde gezeigt, dass es Sprachen A und B gibt, so dass p^A= Np^A und P^B≠ np^B (Baker, Gill und Solovay 1975). Die Tatsache, dass die P = NP -Frage beide Wege relativiert, wird als Beweis dafür angesehen, dass die Beantwortung dieser Frage schwierig ist, da eine Beweistechnik das relativiert (d. H. Unberührt durch die Zugabe eines Orakels) beantwortet die p = np -Frage nicht. Die meisten Beweistechniken relativieren.

Man kann den Fall betrachten, in dem ein Orakel zufällig aus allen möglichen Orakel (ein unendlicher Satz) ausgewählt wird. In diesem Fall wurde gezeigt, dass mit Wahrscheinlichkeit 1, p^A≠ np^A (Bennett und Gill 1981). Wenn eine Frage für fast alle Orakel wahr ist, soll sie wahr sein Für ein zufälliges Orakel. Diese Auswahl der Terminologie wird durch die Tatsache gerechtfertigt, dass zufällige Orakel eine Aussage nur mit Wahrscheinlichkeit von 0 oder 1 unterstützen. (Dies folgt aus Kolmogorovs Null -ein -Gesetz.) Dies ist nur ein schwacher Beweis dafür, dass p ≠ np, da eine Aussage für ein zufälliges Orakel, aber für gewöhnliche Turing -Maschinen falsch sein kann; Zum Beispiel IP^A PSPACE^A für ein zufälliges Orakel a aber IP = PSPACE (Chang et al., 1994).

Orakel und Stoppprobleme

Eine Maschine mit einem Orakel für die Problem stoppen Kann bestimmen, ob bestimmte Turing -Maschinen bestimmte Eingaben anhalten, aber im Allgemeinen kann es nicht bestimmen, ob Maschinen, die sich selbst entsprechen, anhalten. Dies schafft eine Hierarchie von Maschinen, die jeweils ein leistungsstärkeres Orakel und ein noch schwierigeres Problem haben. Diese Hierarchie von Maschinen kann verwendet werden, um die zu definieren arithmetische Hierarchie (Börger 1989).

Anwendungen zur Kryptographie

Im KryptographieOrakel werden verwendet, um Argumente für die Sicherheit von kryptografischen Protokollen vorzunehmen, bei denen a Hash-Funktion wird genutzt. EIN Sicherheitsreduzierung Denn das Protokoll wird in dem Fall gegeben, in dem anstelle einer Hash -Funktion a zufälliges Orakel beantwortet jede Abfrage zufällig, aber konsequent; Es wird angenommen, dass das Orakel allen Parteien, einschließlich des Angreifers, wie die Hash -Funktion ist. Ein solcher Beweis zeigt, dass der Angreifer nicht das harte Problem im Zentrum der Sicherheitsreduzierung löst, er eine interessante Eigenschaft der Hash -Funktion nutzen muss, um das Protokoll zu brechen. Sie können die Hash -Funktion nicht als schwarze Box behandeln (d. H. Als zufälliges Orakel).

Siehe auch

Verweise

Akeo Adachi, Grundlagen der Berechnungstheorie, Ohmsha, 1990.
T. P. Baker, J. Gill, R. Solovay. Relativierungen des p =? NP -Frage. Siam Journal über Computing4 (4): 431-442 (1975)
C. H. Bennett, J. Gill. Relativ zu einem zufälligen Orakel a, p^A! = Np^A! = Co-np^A mit Wahrscheinlichkeit 1. Siam Journal on Computing, 10 (1): 96-113 (1981)
Egon Börger. "Berechnbarkeit, Komplexität, Logik". North-Holland, 1989.
Richard Chang, Benny Chor, Od Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan, Pankaj Rohatgi. Die zufällige Orakelhypothese ist falsch. Journal of Computer and System Sciences, Band 49, Ausgabe 1, S. 24–39. August 1994. ISSN 0022-0000. http://citeseer.ist.psu.edu/282397.html
Martin Davis, Editor: Die unentscheidbaren, grundlegenden Arbeiten zu unentscheidbaren Aussagen, unlösbaren Problemen und berechnungsfähigen Funktionen, Raven Press, New York, 1965. Turings Papier befindet sich in diesem Band. Zu den Arbeiten gehören die von Gödel, Church, Rosser, Kleene und Post.
Christos Papadimitriou. Rechenkomplexität. Addison-Wesley, 1994. Abschnitt 14.3: Oracles, S. 339–343.
Hartley Rogers, Jr., Theorie der rekursiven Funktionen und effektiver Berechnbarkeit, McGraw-Hill, 1967.
Michael Sipser. Introduction to the Theory of Computation. PWS Publishing, 1997. ISBN0-534-94728-x. Abschnitt 9.2: Relativierung, S. 318–321.
Robert I. Soare, Rekursiv aufzählbare Sätze und Grad, Perspektiven in der mathematischen Logik, Springer, 1987.
Alan Turing, Logiksysteme, die auf Ordnern basieren, Proc. London Math. Soc., 451939
Dieter van Melkebeek, Zufälligkeit und Vollständigkeit in der Computerkomplexität, Vorlesungen in Informatik 1950, Springer, 2000.