Algorytmy SC ^ 2 dla łączności st

Savitch podał algorytm deterministyczny do rozwiązania łączności st przy użyciu przestrzeni , sugerując, że N L ⊆ D S P A C E ( log 2 n ) . Algorytm Savitcha działa w czasie . Poważnym otwartym problemem jest to, czy łączność st może zostać rozwiązana przez algorytm deterministyczny w czasie wielomianowym i przestrzeni tj. Czy . , który leży między i$O({\log}^2{n})$$NL \subseteq DSPACE({\log}^2{n})$ O ( log 2 n ) N L ⊆ S C 2 R L L N $2^{O({\log}^2{n})}$$O({\log}^2{n})$$NL \subseteq SC^2$$RL$$L$$NL$, wiadomo, że występuje w . Stąd osiągalność na ukierunkowanych wykresach z wielomianowym czasem mieszania jest w S C 2 .$SC^2$$SC^2$

Szukam specjalnych przypadków łączności st (które nie są znane w ), które mają algorytmy S C 2 . Czy coś wiadomo na temat grafów płaskich, płaskich DAG? Należy zauważyć, że łączność st w DAG pozostaje kompletna dla NL.$L$$SC^2$

Istnieją dwie powiązane klasy złożoności w które są również w LogDCFL , co umieszcza je w SC 2 (autor Cook ). $\text{NL}$$\text{LogDCFL}$$\text{SC}^2$

• Pierwszym jest , dla „Reach-jednoznacznej przestrzeni logów”, która ma osiągalność w namorzynach (wykresy, na których każda para wierzchołków ma co najwyżej jedną ukierunkowaną ścieżkę między nimi) jako kompletny problem. Ta klasa była już omawiana .$\text{RUL}$
• Drugi to , który ma pełną dostępność dla wykresów z co najwyżej wielomianową liczbą ścieżek między dowolną parą wierzchołków.$\text{ReachFewL}$

Przeprowadzenie przeszukiwania tych wykresów w pierwszej kolejności za pomocą stosu gwarantuje, że zajmie to czas wielomianowy, więc klasy te znajdują się w .$\text{LogDCFL} \subseteq \text{SC}^2$

Ostatnia konferencja złożoności wykazała pewne postępy w tej kwestii. Osiągalność płasko DAG z źródła mogą być rozwiązane w O ( log n ) przestrzeni$O(\log n)$$O(\log n)$ .

Oto także ostatnia ankieta przeprowadzona przez Allendera: „Problemy z osiągalnością: aktualizacja”