Czy jest jakieś uzasadnienie, aby sądzić, że

Zastanawiam się, czy jest jakieś uzasadnienie, by wierzyć, że czy wierzyć, że ? $NL=L$ $NL\neq L$

Wiadomo, że . W literaturze derandomization z jest dość przekonanie, że . Czy ktoś wie o niektórych artykułach lub pomysłach przekonujących, że ? $NL \subset L^2$ $RL$ $RL=L$ $NL\neq L$

— Klim
źródło

Po pierwsze, chciałbym przytoczyć sceptycyzm że . Jak wykazano, że łączność bezkierunkowego grafu jest w (Reingold) i że (Immerman-Szelepcsényi), myślę, że zaufanie do tylko spadło. Niektórzy wybitni badacze nigdy nie mieli silnego przekonania. Na przykład Juris Hartmanis (założyciel działu CS w Cornell i zdobywca nagrody Turinga) powiedział: $L \neq NL$ $L$ $NL=coNL$ $L \neq NL$

Uważamy, że NLOGSPACE różni się od LOGSPACE, ale nie z taką samą głębią przekonania, jak w przypadku innych klas złożoności. (Źródło)

Wiem, że powiedział podobne rzeczy w literaturze już w latach 70-tych.

Jest pewne dowody na , chociaż nie jest przypadkowy. Odnotowano pracy na udowodnienie przestrzeń dolną granicę dla - łączności (kanoniczna -Complete problem) w ograniczonym modeli obliczeniowych. Modele te są wystarczająco silne, aby uruchomić algorytm twierdzenia Savitcha (który daje algorytm przestrzenny ), ale okazuje się, że nie są wystarczająco silne, aby zrobić asymptotycznie lepiej. Zobacz artykuł „Ciasne dolne granice dla st-Connectivity w modelu NNJAG” $L=NL$ $s$ $t$ $NL$ $O(\log^2 n)$ . Te dolne granice NNJAG pokazują, że jeśli możliwe jest pokonanie twierdzenia Savitcha, a nawet uzyskanie , z pewnością trzeba wymyślić algorytm bardzo różny od Savitcha. $NL \subseteq SPACE[o(\log^2 n)]$

Mimo to nie znam żadnych nieoczekiwanych, nieoczekiwanych konsekwencji formalnych, które wynikają z (z wyjątkiem oczywistych). Ponownie, jest to przede wszystkim dlatego, że wiemy już takie rzeczy jak . $L=NL$ $NL=coNL$

— Ryan Williams
źródło

Ryan, czy modele, w których możesz udowodnić dolną granicę

prowadzić do nieukierunkowanej łączności w przestrzeni

? Jeśli są to modele niejednorodne, myślę, że powinno być łatwo wdrożyć algorytm oparty na uniwersalnych sekwencjach przechodzenia, nawet w bardzo ograniczonym modelu

Ω (\log^{2} n)

$\Omega(\log^2 n)$

O (\log n)

$O(\log n)$

— Luca Trevisan

@Luca, artykuł, który Ryan cytuje przez Edmondsa i in. zauważa, że nieukierunkowaną łączność można rozwiązać w przestrzeni

i czasie wielomianowym za pomocą losowego algorytmu wykorzystującego uniwersalne sekwencje przechodzenia. Podejrzewam, że można go zdekandomizować „a la” Reingolda, pozostając w modelu NNJAG, ale nie sprawdziłem.

O (\log n)

$O(\log n)$

— arnab

Myślę, że model może wykonywać nieukierunkowaną łączność na zwykłych wykresach w przestrzeni

. Strona 4 zawiera opis modelu. Dozwolone jest poruszanie się kamyków

po węzłach wykresu (dla nas niech

„stany” oraz funkcja przejścia, która przyjmuje stan i indeks węzła kamykowego i wyprowadza indeks krawędzi przesuwać kamyk. (Krawędzie wierzchołka

są indeksowane

.) Używając

O (\log n)

$O(\log n)$

p

$p$

p = 1

$p=1$

q

$q$

v

$v$

0, \dots, d

$0,\ldots,d$

q = n^{O (1)}

$q=n^{O(1)}$ stwierdza, że możemy zakodować uniwersalną sekwencję ruchu. Wykorzystanie miejsca przez NNJAG jest zdefiniowane jako

którym w tym przypadku jest

p \log n + \log q

$p \log n + \log q$

O (\log n)

$O(\log n)$

— Ryan Williams