Kontynuując poprzednie pytanie ,
jakie są najlepsze obecne dolne granice przestrzeni dla SAT?
Przez spację dolną rozumiem tutaj liczbę komórek taśmy roboczej używanych przez maszynę Turinga, która używa binarnego alfabetu taśmy roboczej. Stały składnik addytywny jest nieunikniony, ponieważ TM może wykorzystywać stany wewnętrzne do symulacji dowolnej stałej liczby komórek taśmy roboczej. Interesuje mnie jednak kontrolowanie stałej multiplikatywnej, która często pozostaje niejawna: zwykła konfiguracja umożliwia dowolną stałą kompresję za pomocą większych alfabetów, więc stała multiplikatywna nie jest tam istotna, ale przy ustalonym alfabecie powinno być możliwe wzięcie tego pod uwagę.
Na przykład SAT wymaga więcej niż miejsca; jeśli nie, wówczas ta górna granica przestrzeni prowadziłaby do symulacji w górnej granicy czasu , a zatem połączona dolna granica czasoprzestrzeni dla SAT zostać naruszone (patrz powiązane pytanie). Wydaje się również, że można ulepszyć ten argument, aby argumentować, że SAT wymaga co najmniej miejsca dla jakiegoś małego dodatniego , czyli około , gdzie jest stałym wykładnikiem w symulacji ograniczonej przestrzenią TM przez ograniczoną czasowo TM.n 1 + o ( 1 ) n 1,801 + o ( 1 ) δ log n + c δ 0,801 / C C
Niestety jest zwykle dość duży (a na pewno co najmniej 2 w zwykłej symulacji, gdzie taśmy TM są najpierw kodowane na pojedynczej taśmie za pomocą większego alfabetu). Takie granice z są raczej słabe i szczególnie interesowałbym się dolną granicą . Bezwarunkowa dolna granica kroków , dla niektórych wystarczająco dużych stałych , oznaczałaby taką dolną granicę poprzez symulację. Jednak dolne granice czasu dla nie są obecnie znane, nie mówiąc już o dużych .
Innymi słowy, szukam czegoś, co byłoby konsekwencją dolnych granic czasu superlinearnego dla SAT, ale które można byłoby uzyskać bardziej bezpośrednio.
źródło
Odpowiedzi:
Wygląda na to, że najlepiej znana granica (w przypadku maszyn Turinga z wieloma taśmami) jest logarytmiczna.
Załóżmy, że kawałków binarnej taśmy roboczej wystarczy, aby zdecydować, czy jakakolwiek bitowa formuła CNF jest zadowalająca, dla wszystkich wystarczająco dużych . Dzięki standardowej symulacji TM ze stanami , która wykorzystuje co najwyżej bitów przestrzeni, może być symulowana przez TM, która ma co najwyżej różne konfiguracje . Za każdym razem, gdy maszyna akceptuje, następuje sekwencja (niedeterministycznych) ruchów, które osiągają stan akceptacji, który jest co najwyżej tak długi, jak ta liczba konfiguracji. Gdy , to najwyżej (zwróć uwagę, że pozostaje takie samo dla wszystkich długości wejściowychn n q s q n s 2 s = 2 s + log n + log s + log q s = Ω ( log n ) 2 s ( 2 + o ( 1 ) ) q n M o ( 1 ) 2 s ( 2 + o ( 1 ) )δlogn n n q s qns2s=2s+logn+logs+logq s=Ω(logn) 2s(2+o(1)) q n ). Na osobnej taśmie licznikowej może najpierw zapisać tę liczbę pojedynczo, a następnie na każdym etapie symulacji usunąć jeden z symboli licznika i zakończyć obliczenia, jeśli kiedykolwiek zabraknie symboli licznika. Stwarza to stały współczynnik narzutu (coś w rodzaju 3), który jest absorbowany przez wykładnik . Stąd kroki są wystarczające.M o(1) 2s(2+o(1))
Z założenia , więc iloczyn czasoprzestrzenny to co najwyżej .δ log n 2 δ log n ( 2 + o ( 1 ) ) = n δ ( 2 + o ( 1 ) )s≤δlogn δlogn2δlogn(2+o(1))=nδ(2+o(1))
Rahul Santhanam wykazał w 2001 r. (Patrz doi: 10.1016 / S0020-0190 (00) 00227-1 ), że produktem czasoprzestrzennym dla maszyny Turinga decydującej o SAT musi być co najmniej ; jego argument dotyczy także niedeterministycznych maszyn. Stąd i przynajmniej bitów binarnej taśmy roboczej są potrzebne.δ ≥ 1 log nΩ(n2−o(1)) δ≥1 logn
Mówiąc bardziej ogólnie, dodatkowe taśmy robocze i większy alfabet taśmy roboczej zmieniają wykładnik o stały współczynnik. To ostatecznie zmniejsza współczynnik , ale dolna granica przestrzeni to wciąż .Ω ( log n )δ Ω(logn)
źródło
Być może możemy w ten sposób udowodnić spację dolną granicę dla SAT (ale nie jestem przekonany do analizy limitu / analizy asymptotycznej, więc moja odpowiedź może być całkowicie błędna).logn
W modelu maszyny Turinga z jedną taśmą wejściową tylko do odczytu i jedną taśmą roboczą, obie na binarnym alfabecie , dla każdego decydującego ze stanami na wejściu o rozmiarze mamy to:c nΣ={0,1} c n
w przeciwnym razie maszyna Turinga zapętli się na zawsze ( komponent reprezentuje wszystkie możliwe konfiguracje taśmy, komponent reprezentuje wejściowe pozycje głowicy taśmy, podczas gdy komponent reprezentuje pozycje głowicy taśmy roboczej). Na jednej taśmie pojedyncza głowica TM na binarnym alfabecie (1) staje się . n S ( n ) T ( n ) ≤ c 2 S ( n ) S ( n )2S(n) n S(n) T(n)≤c2S(n)S(n)
Mnożąc oba warunki przez i stosując ogólny kompromis czasoprzestrzenny dla SAT, otrzymujemy:S(n)
Zatem wybranie spacji górnej granicy, takiej jak dla SAT, doprowadziłoby do sprzeczności, w rzeczy samejS(n)≤(logn)1−ϵ
źródło