Najlepsza bieżąca dolna granica dla SAT?

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. $\log\log n + c$ $n^{1+o(1)}$ $n^{1.801+o(1)}$ $\delta\log n + c$ $\delta$ $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 . $C$ $\delta \ll 1$ $\log n + c$ $\Omega(n^d)$ $d > 1$ $\Omega(n^d)$ $d>1$ $d$

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.

— András Salamon
źródło

jak w tej innej odpowiedzi (np. RW), osobne skupienie się na dolnych granicach czasu lub przestrzeni wydaje się być poza zasięgiem i ma tylko słabe / ogólne znane granice, a wiodące badania w tym obszarze wydają się prowadzić do stosunkowo nowej koncepcji połączonej złożoności czasoprzestrzennej.

— vzn

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ściowych $\delta\log n$ $n$ $n$ $q$ $s$ $qns2^s = 2^{s+\log n + \log s + \log q}$ $s = \Omega(\log n)$ $2^{s(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)$ $2^{s(2+o(1))}$

Z założenia , więc iloczyn czasoprzestrzenny to co najwyżej . $s \le \delta\log n$ $\delta\log n2^{\delta\log n(2+o(1))} = n^{\delta(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. $\Omega(n^{2-o(1)})$ $\delta \ge 1$ $\log n$

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ąż . $\delta$ $\Omega(\log n)$

— András Salamon
ź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). $\log n$

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: $\Sigma = \{0,1\}$ $c$ $n$

T (n) \leq c 2^{S (n)} n S (n) (1)

$T(n) \leq c \, 2^{S(n)} \, n \, S(n) \quad (1)$

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ę . $2^{S(n)}$ $n$ $S(n)$ $T(n) \leq c 2^{S(n)} S(n)$

Mnożąc oba warunki przez i stosując ogólny kompromis czasoprzestrzenny dla SAT, otrzymujemy: $S(n)$

n^{1.801 + o (1)} \leq S (n) \cdot T (n) \leq c S (n)^{2} 2^{S (n)} n

$n^{1.801+o(1)} \leq S(n)\cdot T(n) \leq c \, S(n)^2 \, 2^{S(n)} \, n$

Zatem wybranie spacji górnej granicy, takiej jak dla SAT, doprowadziłoby do sprzeczności, w rzeczy samej $S(n) \leq (\log n)^{1 - \epsilon}$

lim_{n \to \infty} \frac{n^{1.801}}{c ((\log n)^{1 - ϵ})^{2} 2^{(\log n)^{1 - ϵ}} n} =

$\lim_{n \to \infty} \frac{n^{1.801}}{ c \, ((\log n)^{1-\epsilon})^2 2^{(\log n)^{1-\epsilon}} n } =$

lim_{n \to \infty} (0.801 \cdot \log n - \log c - 2 (1 - ϵ) \log (\log n) - (\log n)^{1 - ϵ}) = \infty

$\lim_{n \to \infty} \Big( 0.801 \cdot \log n - \log c - 2 (1- \epsilon) \log (\log n) - (\log n)^{1-\epsilon}\Big) = \infty$

— Marzio De Biasi
źródło

Wydaje się, że istnieją co najmniej dwa ogólne sposoby wykazania, że górna granica prowadzi do sprzeczności. Przede wszystkim, że chodziło używając (zasadniczo identyczne, lecz nieco łatwiejsze w użyciu) nierówności dla pewnej stałej . Ostatni etap podania może być także silniejszy jako przeciwieństwo następuje nawet o .

o (\log n)

$o(\log n)$

T (n) \leq 2^{\log n + C . S (n)}

$T(n) \le 2^{\log n + C.S(n)}$

C

$C$

S (n) \leq δ \log n

$S(n) \le \delta\log n$

δ < 0.801 / C

$\delta < 0.801/C$

— András Salamon,

@ AndrásSalamon: po stronie nie można oczekiwać łatwych ulepszeń: od S. Bussa i R. Williamsa. Ograniczenia w dowodach wymiany alternatywnej dla dolnych granic czasoprzestrzeni, 2012: „Pokazujemy, że nowe techniki są możliwe do udowodnienia, aby udowodnić lepsze dolne granice czasoprzestrzeni dla problemu satysfakcji. To znaczy metoda„ wymiany alternatywnej proofs ”użyte do ustalenia, że SAT nie może być rozwiązany w czasie i spacja nie może udowodnić time dolna granica, dla każdego ". Masz jakiś pomysł :-)?

S \cdot T

$S\cdot T$

n^{2 \cos (π / 7)}

$n^{2\cos(\pi /7)}$

n^{o (1)}

$n^{o(1)}$

n^{2 \cos (π / 7)} + ϵ

$n^{2\cos(\pi /7)}+\epsilon$

ϵ > 0

$\epsilon >0$

— Marzio De Biasi

Myślę, że jest to tak daleko, jak to możliwe, używając granic czasoprzestrzennych, właśnie dlatego, że podejście Ryana jest tak daleko, jak to możliwe.

— András Salamon

Aby nawet zapisać instancję SAT potrzebujesz i przeczytaj ją . Czy to nie dowodzi, że ST dolna granica?

Ω (n)

$\Omega(n)$

Ω (n)

$\Omega(n)$

Ω (n^{2})

$\Omega(n^2)$

— T ....

@Turbo, nie jest jasne, czy każdy algorytm decydujący o SAT musi przechowywać instancję: udowodnienie, że dolna granica przestrzeni deterministycznej bitowej pokaże .

Ω (n)

$\Omega(n)$

L ⊊ N P

$\mathsf{L} \subsetneq \mathsf{NP}$

— András Salamon