Jak udowodnić, że USTCONN wymaga przestrzeni logarytmicznej?

USTCONN to problem, który wymaga podjęcia decyzji, czy istnieje ścieżka od wierzchołka źródłowego $s$ do wierzchołka docelowego $t$ na wykresie $G$ , gdzie wszystkie są podane jako część danych wejściowych.

Omer Reingold wykazał, że USTCONN znajduje się w L (doi: 10.1145 / 1391289.1391291 ). Dowód konstruuje ekspander o stałym stopniu za pomocą produktu zygzakowatego. Ekspander o stałym stopniu ma średnicę logarytmiczną, a następnie można sprawdzić wszystkie możliwe ścieżki za pomocą stałej liczby znaczników wielkości logarytmicznej.

Wynik Reingolda daje logarytmiczną górną granicę złożoności przestrzeni USTCONN, rozwiązując złożoność przestrzeni „aż do stałego współczynnika” zgodnie z dokumentem. Jestem ciekawy odpowiedniej dolnej granicy, o której nigdzie indziej nie wspomniano.

Jak udowodnić, że w najgorszym przypadku USTCONN jest wymagana przestrzeń logarytmiczna?

Edycja: Napraw reprezentację wejściową jako macierz przylegania $N \times N$ leżącego u jej podstaw symetrycznego prostego wykresu $N$ -vertex, z rzędami wymienionymi kolejno, aby utworzyć ciąg $N^2$ bitowy.

Lewis i Papadimitriou wykazali (doi: 10.1016 / 0304-3975 (82) 90058-5 ), że USTCONN jest kompletny SL, co z wynikiem Reingolda oznacza, że ​​SL = L. Savitch wykazał (doi: 10.1016 / S0022-0000 (70) 80006-X ), że $\text{NSPACE}(n) \subseteq \text{DSPACE}(n^2)$ . Dalsze $\text{DSPACE}(f(n)) = \text{DSPACE}(1)$ dla dowolnej funkcji obliczalnej $f(n) = o(\log\log n)$przez Stearns, Hartmanis i Lewis (doi: 10.1109 / FOCS.1965.11 ), więc potrzeba co najmniej $\Omega(\log\log n)$ dla USTCONN. Wreszcie, zwykłe klasy, o których wiadomo, że są poniżej L (takie jak $\text{NC}^1$ ), są zdefiniowane w kategoriach obwodów i nie są oczywiście porównywalne z żadną klasą zdefiniowaną w kategoriach ograniczonej przestrzeni.

O ile widzę, pozostawia to otwartą (co mało prawdopodobne) możliwość, że istnieje jeszcze lepszy deterministyczny algorytm, który wykorzystuje tylko przestrzeń $O((\log n)^\delta)$ ale $\Omega(\log \log n)$ , dla niektórych $\delta < 1$ , lub nawet niedeterministyczny algorytm USTCONN że zastosowania $o((\log n)^{1/2})$ przestrzeń.

$\text{DSPACE}(o(f(n)) \subsetneq \text{DSPACE}(f(n))$$f(n)$$\text{DSPACE}(o(\log n))$

Tak długo, jak istnieje język w L, który wymaga przestrzeni logarytmicznej, to pokazanie, że USTCONN jest kompletne dla L pod ściśle „słabszym” niż redukcja przestrzeni logicznej, dałoby pożądaną dolną granicę.

Czy USTCONN jest kompletny dla L przy redukcji wymagającej spacji ?$o(\log n)$

Immerman wykazał (doi: 10.1137 / 0216051 ), że wersja ukierunkowanej osiągalności, w której pożądana ścieżka (ale nie sam wykres) jest deterministyczna, jest kompletna dla L przy redukcjach pierwszego rzędu, które są obliczalne przez obwody AC . Być może można to następnie dostosować, aby wykazać, że USTCONN jest kompletny dla L przy obniżeniu FO. Jednakże, chociaż AC jest ściśle zawarty w L, AC ponownie jest klasą obwodów i nie jestem świadomy żadnego sposobu wykonywania redukcji FO w przestrzeni sublogarytmicznej.$^0$$^0$$^0$

Edytuj 2015-07-14: Ciekawym zagadnieniem filozoficznym jest to, czy wykorzystanie miejsca przez TM powinno obejmować wielkość indeksu na wejściu (umożliwiając w ten sposób losowy dostęp do wejścia, ale wymaga dodatkowego bitu, jeśli rozmiar wejścia podwaja się ) lub czy przestrzeń używana przez bazę TM jest liczbą kwadratów taśmy roboczej odwiedzonych podczas obliczeń (która zakłada, że ​​głowica taśmy wejściowej jest stała i nie zmienia się, gdy rozmiar taśmy wejściowej podwaja się). Poprzednia definicja stylu RAM natychmiast określa dolną granicę dla dowolnego obszaru logówobliczenia i modeluje bieżące komputery, które śledzą bieżącą pozycję w pliku jako przesunięcie względem początku pliku. Ta ostatnia klasyczna definicja zakłada taśmę w kształcie papieru ze stałą głowicą czytającą, która nie wie nic o taśmie poza bieżącym symbolem wejściowym, co prawdopodobnie jest tym, co zamierzał Turing w swoim artykule z 1937 roku.

Argumenty heurystyczne, takie jak komentarz Thomasa, że ​​nie jest nawet możliwe indeksowanie danych wejściowych bitami , wydają się przyjmować nowoczesną definicję stylu RAM. Stearns / Hartmanis / Lewis używają definicji stylu TM, podobnie jak większość klasycznych prac w obliczeniach ograniczonych przestrzenią.$o(\log n)$

Można udowodnić dolną granicę przestrzeni logicznej dla USTCONN reprezentowaną jako macierz przylegania, zauważając, że jednoargumentowy język idealnych kwadratów wymaga przestrzeni logicznej do rozpoznania (patrz Rūsiņš Freivalds, Modele obliczeń, Riemann Hypothesis i Classical Mathematics , SOFSEM 1998, LNCS 1521, 89 –106. Doi: 10.1007 / 3-540-49477-4_6 ( preprint)). Następnie ta sama dolna granica dotyczy USTCONN z reprezentacją macierzy przyległości. Jest to być może zbyt wielki oszust: zazwyczaj egzekwowanie obietnicy w przypadku problemu z obietnicą ma być łatwe w porównaniu do rzeczywistego problemu, ale tutaj egzekwowanie obietnicy, że dane wejściowe są wykresem, już określa dolną granicę. Byłoby miło widzieć argument za dolną granicą obszaru logów dla problemu z obietnicą, w którym dane wejściowe są gwarantowane z języka .$\{\{0,1\}^{N \times N} \mid N=1,2,\dots\}$

Artykuł Liczenie kwantyfikatorów, relacje następców i przestrzeń logarytmiczna Kousha Etessami udowadnia, że ​​problem (który polega zasadniczo na sprawdzeniu, czy wierzchołek poprzedza wierzchołek na zdeklasowanym jednym wykresie , który ma być ścieżką ) jest twardy w projekcjach wolnych od kwantyfikatora.$\mathbf{ORD}$$s$$t$$G$$\mathsf{L}$

Problem można zredukować do problemu , dzięki -reductions: Biorąc pod uwagę instancję$\mathbf{ORD}$$\mathbf{USTCONN}$$\mathsf{FO}$$\langle G,s,t\rangle$$\mathbf{ORD}$$t$$u \rightarrow v$$\{u,v\}$$\mathbf{USTCONN}$$s,t$są połączone na wynikowym wykresie. (Uwaga: redukcję można prawdopodobnie zwiększyć jeszcze).