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

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

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

Po pierwsze, chciałbym przytoczyć sceptycyzm że . Jak wykazano, że łączność bezkierunkowego grafu jest w L (Reingold) i że N L = c o N L (Immerman-Szelepcsényi), myślę, że zaufanie do L ≠ N L 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 s - t łączności (kanoniczna N L -Complete problem) w ograniczonym modeli obliczeniowych. Modele te są wystarczająco silne, aby uruchomić algorytm twierdzenia Savitcha (który daje algorytm przestrzenny O ( log 2 n ) ), 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 N L = C ° N L .$L=NL$$NL=coNL$