Jakie są obecnie najlepsze dolne granice 3SAT?

Odpowiedzi:

43

O ile mi wiadomo, najbardziej znana dolna granica czasu „niezależnego od modelu” dla SAT jest następująca. Niech i S będą czasem wykonywania i przestrzenią dowolnego algorytmu SAT. Zatem musimy mieć T S n 2 cos ( π / 7 ) - o ( 1 ) nieskończenie często. Uwaga 2 cos ( π / 7 ) 1,801 . (Wynik, który przytacza Suresh, jest nieco przestarzały.) Ten wynik pojawił się w STACS 2010, ale jest to rozszerzony streszczenie znacznie dłuższego papieru, który można uzyskać tutaj:T.S.T.S.n2)sałata(π/7)-o(1)2)sałata(π/7)1,801http://www.cs.cmu.edu/~ryanw/automated-lbs.pdf

Oczywiście powyższa praca opiera się na wielu wcześniejszych pracach wspomnianych na blogu Liptona (patrz odpowiedź Suresha). Ponadto, gdy S związana z przestrzenią zbliża się do n, czas dolnej granicy T również zbliża się do n. Możesz udowodnić lepszy „kompromis czasoprzestrzenny” w tym systemie; patrz badanie Dietera van Melkebeeka dotyczące dolnych granic SAT w czasoprzestrzeni z 2008 roku.

Jeśli ograniczysz się do wielowarstwowych maszyn Turinga, możesz udowodnić nieskończenie często. Zostało to udowodnione przez Rahula Santhanama i wynika z podobnej dolnej granicy znanej z PALINDROMES w tym modelu. Uważamy, że powinieneś być w stanie udowodnić kwadratową dolną granicę, która jest „niezależna od modelu”, ale która była nieuchwytna przez pewien czas.T.S.n2)-o(1)

W przypadku obwodów nierównomiernych z ograniczonym wachlowaniem nie znam dolnej granicy lepszej niż .logn

Ryan Williams
źródło
2
pracujemy nad tym. Zobacz ten link: meta.cstheory.stackexchange.com/questions/3/latex-math-support
Suresh Venkat
2
@vinayak: Stwierdzenie, w którym „nieskończenie często” pojawia się powyżej, jest zaprzeczeniem: „Istnieje algorytm SAT taki, że , prawie wszędzie.” Negacja „prawie wszędzie” jest „nieskończenie często”, oznacza to, że dla każdego algorytmu istnieje nieskończenie wiele instancji, w których nie rozwiązuje instancji za pomocą niewielkiego iloczynu czasu i przestrzeni. T.S.n2)sałata(π/7)+o(1)
Ryan Williams,
2
To niesamowite, że mamy lepsze dolne granice dla naprawdę łatwego problemu odróżnienia elementu ( T S = Ω ( n 2 - o ( 1 ) ) Yao) niż w przypadku SAT! T.S.T.S.=Ω(n2)-o(1))
Warren Schudy,
1
@ Warren, niezupełnie, o ile wiem. Dolne granice, takie jak Yao, dotyczą modelu rozgałęziającego opartego na porównaniu , który nie jest tak ekspresyjny jak maszyna o swobodnym dostępie ogólnego przeznaczenia. Można sobie wyobrazić rozwiązanie odrębności elementu bez jakichkolwiek bezpośrednich porównań między elementami.
Ryan Williams,
1
@Turbo najlepsza dolna granica dla 3sat z liniowo wieloma klauzulami jest taka sama, jak napisałem, ponieważ redukcja z sat do 3sat jest niezwykle lokalna. Pokażą to również literatura na ten temat.
Ryan Williams
17

o(n)ndodo3)

Suresh Venkat
źródło
1
no(1)o(n)
11

Ω(ndo)do>1

Lew Reyzin
źródło
4

Moje rozumowanie jest takie samo jak Lwa Reyzina. Możliwe jest, że istnieje deterministyczny kompletny algorytm dla SAT, który działa w przestrzeni O (n) i czasie O (n). To niesamowite, że istnienie tak wydajnego algorytmu nie jest zabronione.

Giorgio Camerani
źródło