Komplexitätstheorie, wenn ein Orakel Teil der Eingabe ist

In der Komplexitätstheorie treten Orakel am häufigsten wie folgt auf: Ein festes Orakel wird beispielsweise einer Turing-Maschine mit bestimmten begrenzten Ressourcen zur Verfügung gestellt, und es wird untersucht, wie das Orakel die Rechenleistung der Maschine erhöht.

Es gibt jedoch eine andere Art und Weise, wie Orakel manchmal auftreten: als Teil der Eingabe . Angenommen, ich möchte Algorithmen zur Berechnung des Volumens eines bestimmten hochdimensionalen Polytops untersuchen. Klassischerweise müsste das Polytop angegeben werden, indem eine Liste seiner Facetten oder eine andere explizite Darstellung bereitgestellt wird. Wir können aber auch das Problem der Berechnung des Volumens eines Polytop darstellen , die von einem angegeben Volumen oracle, das die Koordinaten eines Punktes im Raum als Eingabe und Ausgabe "ja" nimmt, wenn und nur wenn der gegebene Punkt innerhalb des Polytops liegt. Dann können wir fragen, welche Rechenressourcen benötigt werden, um das Volumen eines auf diese Weise spezifizierten Polytops zu berechnen. In diesem speziellen Fall haben wir das sehr schöne polynomielle Zeitnäherungsschema von Dyer, Frieze und Kannan und interessanterweise aus der Sicht der Komplexitätstheorie einen Beweis dafür, dass Zufälligkeit in einer für dieses Problem wesentlichen Weise hilfreich ist, da kein deterministischer Algorithmus dies kann Leistung wie der Dyer-Frieze-Kannan-Algorithmus.

Gibt es eine systematische Möglichkeit, die Komplexitätstheorie von Problemen zu untersuchen, bei denen Orakel als Teil des Inputs bereitgestellt werden? Reduziert es sich irgendwie auf die übliche Theorie der Komplexitätsklassen mit Orakeln? Ich vermute nein, und da es zu viele verschiedene Möglichkeiten gibt, ein Orakel als Teil der Eingabe bereitzustellen, muss jedes Problem dieser Art ad hoc behandelt werden. Ich würde mich jedoch freuen, in diesem Punkt als falsch erwiesen zu werden.

Es heißt Typ-2-Komplexitätstheorie. Es gibt einen Aufsatz von Cook, Impagliazzo und Yamakami, der die Theorie der generischen Orakel gut aufgreift.

Dies muss alles andere als eine vollständige Antwort sein, aber es deutet hoffentlich auf einige Orte hin, die man sich ansehen sollte.

Probleme, bei denen ein Teil der Eingabe als Orakel angegeben wird, werden manchmal als Probleme mit impliziter Eingabe bezeichnet . Es ist ein praktisches Modell, z. B. bei der Untersuchung probabilistisch überprüfbarer Beweise .

Ein wichtiges Untersuchungsgebiet zu den Problemen mit impliziter Eingabe ist die Theorie der Abfragekomplexität , bei der die Komplexität ausschließlich anhand der Anzahl der Abfragen an das Eingabeorakel gemessen wird, wobei der Rechenaufwand zwischen den Abfragen unberücksichtigt bleibt. Viele Komplexitätsklassen haben ihre Entsprechungen in Bezug auf die Abfragekomplexität, und eine Trennung zwischen Komplexitätsklassen in Bezug auf die Abfragekomplexität impliziert häufig eine Orakeltrennung zwischen den entsprechenden Klassen in Bezug auf die Rechenkomplexität.

Ich kenne die Untersuchung von Komplexitätsklassen von Problemen mit implizitem Input (und nicht individuellen Problemen) unter Berücksichtigung der Rechenkosten nicht, aber wahrscheinlich wissen es einige Leute.

Das Modell, in dem die Eingabe als Orakel bereitgestellt wird, wird in der Berechenbarkeitstheorie und der berechenbaren Analyse untersucht. Eines der Modelle, das Ihren Vorstellungen nahe zu kommen scheint, ist das TTE-Modell (Type Two Effectivity). Eine gute Referenz dafür ist Klaus Weihrauchs Buch " Computable Analysis ". Er spricht auch kurz über Komplexität in Kapitel 7.

Das Buch " Computational Complexity of Real Functions " von Ker-I Ko beschreibt ein anderes Modell des Zugangs zum Orakel, das für Komplexität besser geeignet zu sein scheint. Die Probleme bei der Darstellung von Objekten höheren Typs und der Methode, auf das Orakel zuzugreifen, sind heikel. Siehe zum Beispiel Stephen A. Cook und Akitoshi Kawamuras kürzlich erschienene Arbeit " Complexity Theory for Operators in Analysis " aus STOC 2010 und seine Doktorarbeit . Eines der Hauptprobleme ist, dass man, um das Modell vernünftig zu machen, der Maschine genügend Zeit geben muss, um die Antworten des Orakels zu verarbeiten (andernfalls kann man nicht einmal den Anwendungsoperator berechnen). Für die Polynomzeit und den Polynomraum können Polynome höherer Ordnung verwendet werden, die auf Stephen A. Cook und Bruce M. Kapron basieren.Eine neue Charakterisierung der Typ-2-Machbarkeit "FOCS 1991 und" Charakterisierungen der realisierbaren Grundfunktionen vom endlichen Typ "STOC 1989.