Ciasne dolne granice twierdzenia Savitcha

Przede wszystkim z góry przepraszam za wszelką głupotę. W żadnym wypadku nie jestem ekspertem od teorii złożoności (a nawet daleko! Jestem studentem, który bierze moją pierwszą klasę z teorii złożoności). Oto moje pytanie. Teraz Twierdzenie Savitcha stwierdza, że Teraz jestem ciekawy, czy ta dolna granica była ścisła, tj. Czy jest to coś wzdłuż linii

NSPACE (f (n)) \subseteq DSPACE ({(f (n))}^{2})

$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right)$

jest nieosiągalny.

NSPACE (f (n)) \subseteq DSPACE ({(f (n))}^{1.9})

$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^{1.9}\right)$

Wydaje się, że należy tu przedstawić prosty argument kombinatoryczny - każdy węzeł na grafie konfiguracji dla deterministycznej maszyny Turinga ma tylko jedną krawędź wychodzącą, podczas gdy każdy węzeł na wykresie konfiguracji dla nie deterministycznej maszyny Turinga może mieć więcej niż jedna krawędź wychodząca. Algorytm Savitcha przekształca wykresy konfiguracji z dowolną liczbą krawędzi wychodzących w grafy konfiguracji z krawędziami wychodzącymi. $<2$

Ponieważ wykres konfiguracji definiuje unikalną bazę TM (nie jestem tego pewien), kombinatoryczny rozmiar tej ostatniej jest prawie na pewno większy niż poprzedni. Ta „różnica” jest może czynnikiem , a może mniej - nie wiem. Oczywiście istnieje wiele drobnych problemów technicznych, które należy rozwiązać, na przykład jak upewnić się, że nie ma żadnych pętli itp., Ale moje pytanie brzmi, czy jest to rozsądny sposób, aby zacząć udowadniać coś takiego. $n^2$

cc.complexity-theory space-bounded

— Gabgoh
źródło

Odpowiedzi:

To dobrze znane otwarte pytanie. W teorii złożoności zobaczysz wiele otwartych pytań, na które możesz się zastanawiać, dlaczego nikt nie zdołał ich rozwiązać. Częściowo dlatego, że potrzebujemy nowych ludzi takich jak Ty, aby pomóc nam je rozwiązać :)

Aby uzyskać najnowszy wynik w tym obszarze, pokazujący, że algorytm Savitcha jest optymalny w niektórych ograniczonych modelach, patrz artykuł FOCS Aarona Potechina .

$G$ $n$ $s,t$ $N$ $G'$ $s',t'$ $G'$ $G$ $s$ $t$ $G$ $s'$ $t'$ $G'$ $N$ $n$

$N$ $2^{\Omega(\log^2 n)} = n^{\Omega(\log n)}$ $L\neq NL$ $N > n^c$ $c$ $N > n^{10}$ $N \geq n^2$

— Boaz Barak
źródło

$L \neq NL$

— Karolina Sołtys
źródło

Dobra uwaga, dzięki :) Na drugie pytanie - czy widzisz jakieś oczywiste wady w kombinatoryjnym podejściu do pokazywania czegoś takiego?

— gabgoh

Twierdzenie Savitcha jest specyficznym algorytmem symulującym niedeterministyczny algorytm przestrzeni f (n) za pomocą funkcji dziel i zwyciężaj z głębokością O (f (n)) (dając f (n) ^ 2). Udowodnienie dolnych granic obejmuje pokazanie, że WSZYSTKIE algorytmy wykorzystujące mniej miejsca zawodzą na niektórych danych wejściowych. To jest powód, dla którego L = NL jest trudne (a P = NP jest trudne).

— Derrick Stolee

N S p a c e (f (n)) \subseteq D S p a c e ((f (n))^{1.9})

$NSpace(f(n)) \subseteq DSpace((f(n))^{1.9})$

f

$f$

\log n

$\log n$

L \neq N L

$L \neq NL$

N S p a c e (f (n)) \subseteq D S p a c e ((f (n))^{1.9})

$NSpace(f(n)) \subseteq DSpace((f(n))^{1.9})$

L

$L$

N L

$NL$