Rechenmodell in SETH

11

Impagliazzo, Paturi und Calabro, Impagliazzo, Paturi führten die Exponential-Time-Hypothese (ETH) und die Strongly Exponential-Time-Hypothese (SETH) ein. Ungefähr sagt SETH, dass es keinen Algorithmus gibt, der SAT in der Zeit löst . 1.99n

Ich fragte mich, was das bedeuten würde, um SETH zu brechen. Wir müssen definitiv einen Algorithmus finden, der SAT in weniger als Schritten löst , aber ich verstehe nicht ganz, welches Rechenmodell wir verwenden sollten. Soweit ich weiß, müssen Ergebnisse, die auf SETH basieren (siehe z. B. Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, Wahlstrom ), keine Annahmen über das zugrunde liegende Berechnungsmodell treffen.2n

Nehmen wir zum Beispiel an, wir haben einen Algorithmus gefunden, der SAT in der Zeit Verwendung des Raums löst . Bedeutet dies automatisch, dass wir eine Turingmaschine finden können, die dieses Problem in der Zeit von löst ? Bricht es SETH?1,5 n 1,99 n1.5n1.5n1.99n

Alex Golovnev
quelle

Antworten:

18

SETH sagt, dass es für alle ein so dass -SAT Zeit benötigt, um im schlimmsten Fall gelöst zu werden. Das Rechenmodell wird im Allgemeinen als Direktzugriffsmaschine oder Zeigermaschinenmodell angesehen, das einen zeitlichen Zugriff von auf einen Speicher von Elementen ermöglicht, und es wird allgemein angenommen, dass es auch mit begrenztem Fehler probabilistisch ist.k k 2 δ n O ( log N ) N.δ<1kk2δnO(logN)N

Soweit ich weiß, ist offen, ob -Zeitalgorithmen für ein solches Modell in Zwei-Band-Turing-Maschinen übersetzt werden können, die in -Zeit ausgeführt werden. Der Nachweis, dass eine solche Übersetzung nicht möglich ist, würde jedoch Multitape-Turing-Maschinen von Maschinen mit wahlfreiem Zugriff trennen, was mehrere sehr interessante Auswirkungen hätte. Zum einen würde es beweisen , dass SAT nicht auflösbar in quasi-linearen Zeit auf Mehrband - Turingmaschinen ist (weil, wenn SAT mit solchen Maschinen multitape gelöst werden könnte, dann Schreib-Lese-Maschinen können 2 δ np o l y ( n )2δn2δnpoly(n)effizient mit Multitape-Turing-Maschinen simuliert werden). Beachten Sie, dass viele rechnerische Grundelemente (wie Sortieren, Schaltungsauswertung, einfache dynamische Programmierung) effizient auf Multitape-Turing-Maschinen implementiert werden können. Eine relevante Referenz für diese Probleme ist Regan, "Über den Unterschied zwischen Turing-Maschinenzeit und Maschinenzeit mit wahlfreiem Zugriff".

Um Ihre spezifischen Fragen zu beantworten: Nein, eine Multitape-Turing-Maschine wird hier nicht automatisch impliziert, aber ja, ein solcher "Algorithmus" für SAT (unter dem üblichen Direktzugriffsmodell) würde SETH brechen.

Ryan Williams
quelle
3
Vielen Dank! Sie haben meine Frage definitiv beantwortet, aber sagt SETH nicht, dass ? δ=1
Alex Golovnev
2
Nicht ganz. Ich habe die Quantifizierer repariert.
Ryan Williams
Was ist mit den Quantencomputern in diesem Zusammenhang? Gibt es in diesem Zusammenhang keine Konsequenzen von Grovers Algorithmus? Gibt es Arbeiten zur Annahme eines Quantenanalogons der ETH?
Martin Schwarz
In Bezug auf Quantenalgorithmen gibt Grover ungefähr Zeit für CNF SAT an. Man könnte aber ein "Quanten-SETH" aufstellen, das behauptet, dass diese Quadratwurzel-Beschleunigung am besten möglich ist.
2n/2
Ryan Williams
Sicher, aber haben diese besser als klassische Beschleunigung und das "Quatum SETH" nicht schon an irgendeiner anderen Stelle in der Komplexitätstheorie irgendwelche Auswirkungen? Ich wundere mich nur.
Martin Schwarz