Inwiefern würde ein SAT-Orakel helfen, polynomiale Zeitalgorithmen zu beschleunigen?

23

Der Zugriff auf ein -Orakel würde für alles in N P - P (vorausgesetzt, die Menge ist nicht leer) eine bedeutende, superpolynomielle Beschleunigung bewirken. Es ist jedoch weniger klar, wie sehr P von diesem Zugang zum Orakel profitieren würde . Natürlich kann die Beschleunigung in P kein Superpolynom sein, aber es kann immer noch ein Polynom sein. Könnten wir zum Beispiel mit einem S A T -Orakel einen kürzesten Weg schneller finden als ohne? Wie wäre es mit anspruchsvolleren Aufgaben wie der Minimierung submodularer Funktionen oder der linearen Programmierung? Würden sie (oder andere natürliche Probleme in P ) von einem S A T profitieren ?SATNPPPPSATPSAT Orakel?

Wenn wir im Allgemeinen ein Problem in finden und ein Orakel dafür verwenden können, welches der Probleme in P könnte dann eine Beschleunigung sehen?NPPP

Andras Farago
quelle
2
Wie schnell ist das Orakel? Wenn es dauert , können mehr Probleme beschleunigt werden als wenn es O ( s 5 ) dauert , wobei s die Größe der SAT-Formel ist. O(s)O(s5)s
Peter Shor
2
@PeterShor Ich gehe davon aus, dass das Orakel beim Empfang einer SAT-Formel als Abfrage in einem einzigen Schritt (konstante Zeit) eine JA- oder NEIN-Antwort zurückgibt, die angibt, ob die Formel erfüllt werden kann oder nicht. Dies ist unabhängig von der Formelgröße. Natürlich muss die Formel konstruiert werden, um abgefragt zu werden. Diese Erstellungszeit ist nicht unabhängig von der Formelgröße und es ist auch problemabhängig, welche Formeln abgefragt werden müssen. Sobald die Formel erstellt ist, wird der Erhalt der Antwort für jede Formel als ein einzelner Schritt gezählt.
Andras Farago
3
Wenn Sie anstelle eines SAT-Orakels ein Orakel zulassen , können Sie damit minimale Schaltkreise für jedes Problem finden. Dies würde ein nahezu optimal Kosten für jedes Problem abgeschrieben (der Grund ist es nur abgeschrieben ist , dass , wenn Sie diese nur einmal verwenden, dann die Größe des Σ 2 S A T Formel Sie aufschreiben , ist im Wesentlichen der Laufzeit der ursprünglichen Poly-Zeit Algorithmus - aber nach diesem Schritt haben Sie eine optimale Schaltung für alle Fälle von Größe n ). Σ2SATΣ2SATn
Joshua Grochow
@ JoshuaGrochow Ihr Kommentar ist sehr interessant! Es wäre großartig, wenn Sie eine Antwort mit mehr Details sehen würden.
Andras Farago

Antworten:

15

Eigentlich Akzeptanz von nichtdeterministischen Turingmaschinen in der Zeit ist O ( t log t ) -Zeit reduzierbar SAT (die Konstruktion über oblivious Simulation ist, siehe Arora-Barak), so typischerweise jederzeit eine nichtdeterministische Maschine ist erheblich schneller als ein determinis Wir werden zumindest eine gewisse Beschleunigung mit einem SAT-Orakel sehen.tO(tlogt)

Um genauer zu sein, denken Sie an Primalitätstests, da die beste Variante des AKS - Algorithmus die Primalität einer Bit - Zahl in der Zeit O ( n 6 zu testen scheintn . Aber wenn wir "old school" gehen, hat Pratt ein nicht deterministisches TM gegeben, um die Primalität in der Zeit O ( n 3) zu bestimmenO(n6polylogn) . Die Akzeptanz dieser Maschine kann (deterministisch) in O ( n 3 reduziert werdenO(n3polylogn) Zeit zu einer SAT-Instanz.O(n3polylogn)

Das 3SUM-Problem kann ein weiteres Beispiel sein, da man eine Lösung zu erraten scheint und sie in subquadratischer Zeit überprüfen kann. Dann kann die Akzeptanz einer solchen Maschine in subquadratischer Zeit auf SAT reduziert werden.

Joe Bebel
quelle
7

Wenn wir im Allgemeinen ein Problem in NP-P finden und ein Orakel dafür verwenden können, welches der Probleme in P könnte dann eine Beschleunigung sehen?

Diese Frage wird direkter bei der Darstellung und der Zeit, die erforderlich ist, um ein Problem auf ein anderes zu reduzieren.

Die Hauptantwort, die ich vor Augen habe, ist ein Orakel der Integer / Linearen Programmierung. Die Entscheidungsversion dieses Problems ist NP-vollständig. Es gibt eine triviale "Reduktion" der linearen Programmierung, da es sich um einen Sonderfall handelt. Ein Orakel für die lineare Programmierung allein (geschweige denn ILP) beschleunigt jedoch viele Probleme, die durch die lineare Programmierung sofort lösbar sind. Sie können in linearer Zeit darauf reduziert werden, indem das Problem als LP umgeschrieben wird. Zum Beispiel kürzeste Wege und andere Strömungsprobleme, Matchings.

Aber ich denke nicht, dass ILP der einzige ist, es ist wahrscheinlich eher so, dass die Leute nicht viel darüber nachgedacht haben, z. B. den kürzesten Weg zu TSP zu verkürzen oder so weiter.

usul
quelle
3

Wenn in einer verwandten Anmerkung (eher ein Kommentar, der als Antwort auf Anfrage veröffentlicht wird) anstelle eines Orakels ein Σ 2 S A T- Orakel zugelassen wird, kann dies verwendet werden, um minimale Schaltkreise für ein Problem in P zu finden (Dies folgt der gleichen Idee wie der Beweis von Karp-Lipton). Dies würde zu nahezu optimalen Amortisationskosten für jedes Problem führen. Der Grund, warum es nur amortisiert wird, ist, dass, wenn Sie es nur einmal verwenden, die Größe der Σ 2 S A T -Formel, die Sie aufschreiben, im Wesentlichen die Laufzeit Ihres ursprünglichen Polyzeit-Algorithmus ist, aber nach diesem Schritt haben Sie dann eine optimale Schaltung für alle Fälle von Größe nSATΣ2SATPΣ2SATn.

Joshua Grochow
quelle
Ich finde diese Antwort sehr interessant, weil es zeigt , dass ein Orakel viel nützlicher / mächtiger als eine sein kann , N P -oracle, auch für praktische Probleme in P ! Natürlich wussten wir, dass N P N PN P (unter der Annahme, dass P H nicht unter der zweiten Ebene zusammenbricht), aber es schien eine ziemlich undurchsichtige theoretische Tatsache zu sein, die nichts mit P zu tun hat . Aber diese Wahrnehmung war falsch, der Unterschied kann sogar für praktische Probleme in P wesentlich sein . (Schade, dass wir weder ein N P noch ein N P habenNPNPNPPNPNPNPPHPPNP Orakel ...)NPNP
Andras Farago
1
@AndrasFarago: Interessanter Punkt! Ich frage mich , ob es eine interessante und natürliche Folge für „praktische Probleme ist “ von Orakeln höher in mit P H . Meine anfängliche Vermutung wäre, dass wir nicht wirklich wissen, was mit der Tatsache zusammenhängt, dass wir nicht wirklich wissen, wie man mehr als ein paar Quantifiziererwechsel sehr gut verwendet: cstheory.stackexchange.com/a/11403/129PPH
Joshua Grochow
@ JoshuaGrochow Ein Problem mit einem höheren Orakel von PH könnte so aussehen. Suchen Sie einen Schaltkreis mit minimaler Größe, der das ursprüngliche Problem korrekt löst. Unter den Schaltkreisen mit minimaler Größe (möglicherweise sind es exponentiell viele) finden Sie einen mit maximaler Energieeffizienz (mit einer gewissen Definition der Energieeffizienz). Unter den resultierenden Schaltkreisen (möglicherweise immer noch exponentiell viele) finden Sie einen mit minimaler Tiefe. Und so weiter, minimieren / maximieren Sie abwechselnd verschiedene Zielfunktionen, möglicherweise viele davon. Ich denke, für verschachtelte min / max Optimierungen würden wir eine Ebene brauchen k + 2 Orakel von PH. kk+2
Andras Farago