Model obliczeniowy w SETH

11

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,99n

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.5n1.5n1,99n

Alex Golovnev
źródło

Odpowiedzi:

18

δ<1kk2)δnO(logN.)N.

2)δn2)δnpoly(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.

Ryan Williams
źródło
3
δ=1
2
Nie do końca. Naprawiłem kwantyfikatory.
Ryan Williams,
Co z komputerami kwantowymi w tym kontekście? Czy w tym kontekście nie ma żadnych konsekwencji algorytmu Grovera? Czy są prace nad przyjęciem kwantowego analogu ETH?
Martin Schwarz
2)n/2)
Jasne, ale czy te lepsze niż klasyczne przyspieszenie i „quatum SETH” nie mają już wpływu na inne miejsce w teorii złożoności? Zastanawiam się.
Martin Schwarz