Jakie są najlepsze dolne granice prądu dla czasu i głębokości obwodu dla 3SAT?
źródło
Jakie są najlepsze dolne granice prądu dla czasu i głębokości obwodu dla 3SAT?
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: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.
W przypadku obwodów nierównomiernych z ograniczonym wachlowaniem nie znam dolnej granicy lepszej niż .
źródło
źródło
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.
źródło