Model obliczeniowy w SETH

Impagliazzo, Paturi i Calabro, Impagliazzo, Paturi wprowadzili hipotezę czasu wykładniczego (ETH) i hipotezę silnie wykładniczego czasu (SETH). Z grubsza, SETH mówi, że nie ma algorytmu, który rozwiązuje SAT w czasie . $1.99^n$

Zastanawiałem się, co to znaczy złamać SETH. Zdecydowanie musimy znaleźć algorytm, który rozwiązuje SAT w mniej niż krokach, ale nie do końca rozumiem, jakiego modelu obliczeniowego powinniśmy użyć. O ile mi wiadomo, wyniki oparte na SETH (patrz np. Cygan, Dell, Lokshtanov, Marks, Nederlof, Okamoto, Paturi, Saurabh, Wahlstrom ) nie muszą przyjmować założeń dotyczących podstawowego modelu obliczeń.$2^n$

Załóżmy na przykład, że znaleźliśmy algorytm, który rozwiązuje SAT w czasie przy użyciu spacji 1,5 n . Czy to automatycznie oznacza, że ​​możemy znaleźć Maszynę Turinga, która rozwiązuje ten problem w czasie 1,99 n ? Czy to łamie SETH?$1.5^n$$1.5^n$$1.99^n$

$\delta < 1$$k$$k$$2^{\delta n}$$O(\log N)$$N$

$2^{\delta n}$$2^{\delta n} \cdot poly(n)$być efektywnie symulowane za pomocą wielowarstwowych maszyn Turinga). Należy zauważyć, że wiele operacji obliczeniowych (takich jak sortowanie, ocena obwodów, proste programowanie dynamiczne) można skutecznie zaimplementować na maszynach Turing z wieloma taśmami. Jednym z istotnych odniesień do tych problemów jest Regan, „O różnicy między czasem maszyny Turinga a czasem maszyny o dostępie swobodnym”.

Aby odpowiedzieć na konkretne pytania: nie, nie sugeruje się tutaj automatycznie maszyny Turinga na wielu taśmach, ale tak, taki „algorytm” dla SAT (w zwykłym modelu z dostępem swobodnym) złamałby SETH.