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 .
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ń.
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?
źródło