Jakie są obecnie najlepsze dolne granice 3SAT?

46

Jakie są najlepsze dolne granice prądu dla czasu i głębokości obwodu dla 3SAT?

cc.complexity-theory lower-bounds sat

— Joe Fitzsimons
źródło

43

O ile mi wiadomo, najbardziej znana dolna granica czasu „niezależnego od modelu” dla SAT jest następująca. Niech i będą czasem wykonywania i przestrzenią dowolnego algorytmu SAT. Zatem musimy mieć nieskończenie często. Uwaga . (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 \cdot S \geq n^{2 \cos(\pi/7) - o(1)}$ $2 \cos(\pi/7) \approx 1.801$ http://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 \cdot S \geq n^{2-o(1)}$

W przypadku obwodów nierównomiernych z ograniczonym wachlowaniem nie znam dolnej granicy lepszej niż . $\log n$

— 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 \cdot S \leq n^{2 \cos (π / 7) + o (1)}

$T \cdot S \leq n^{2 \cos(\pi/7)+o(1)}$

— Ryan Williams,

2

To niesamowite, że mamy lepsze dolne granice

dla naprawdę łatwego problemu odróżnienia elementu (

Yao) niż w przypadku SAT!

T \cdot S

$T \cdot S$

T \cdot S = Ω (n^{2 - o (1)})

$T \cdot S = \Omega(n^{2-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)$ $n^c$ $c$ $\sqrt{3}$

— Suresh Venkat
źródło

1

n^{o (1)}

$n^{o(1)}$

o (n)

$o(n)$

11

$\Omega(n^c)$ $c > 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