Rechenmodell in SETH

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.99^n$

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.$2^n$

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 $1.5^n$$1.5^n$$1.99^n$

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 ) $\delta < 1$$k$$k$$2^{\delta n}$$O(\log N)$$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 δ n ⋅ p o l y ( n $2^{\delta n}$$2^{\delta n} \cdot poly(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.