Wydajne algorytmy przestrzeni logów

17

Łatwo zauważyć, że każdy problem, który można rozstrzygnąć w deterministycznej przestrzeni logicznej ( ), pojawia się co najwyżej w czasie wielomianowym ( ). Wiele znanych algorytmów przestrzeni logicznej (na przykład: nieukierowana łączność st, izomorfizm płaskiego wykresu) działa w gdzie jest niesamowicie duże. $L$ $P$ $O(n^k)$ $k$

Szukam przykładów problemów naturalnych, o których wiadomo, że można je rozwiązać jednocześnie w deterministycznej przestrzeni logów i czasie gdzie . Nie ma nic specjalnego w 10. Patrząc na obecnie znane algorytmy przestrzeni logicznej, myślę, że jest wystarczająco interesujące. $O(n^k)$ $k \leq 10$ $k \leq 10$
Aleliunas i in. pokazał, że nieukierowana łączność st jest w (losowy obszar logów). Czas działania ich algorytmu wynosi . Czy istnieją naturalne problemy, które można rozwiązać jednocześnie w i czas liniowy (lub) w pobliżu czasie liniowym czyli czas? $RL$ $O(n^3)$ $RL$ $O(n{\log}^i{n})$

Edycja: Aby uczynić rzeczy bardziej interesującymi, spójrzmy na problemy o twardości co najmniej . $NC^1$

cc.complexity-theory space-bounded space-time-tradeoff

— Shiva Kintali
źródło

Czy istnieje analiza czasowa wersji logicznej twierdzenia Courcelle'a? eccc.uni-trier.de/report/2010/062

— Hsien-Chih Chang 張顯之

10

Wydaje mi się, że osiągalność Planar DAG (SSPD) z jednego źródła z pojedynczym zlewem ma algorytm przestrzeni logicznej o skromnym czasie działania ( ?). Nie jestem pewny co do algorytmu SMPD (Single-Source Multiple-sink Planar DAG Reachability). $O(n^2)$

Ref: Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Problemy z osiągalnością wykresów płaskich i siatkowych. Teoria Oblicz. Syst. 45 (4): 675–723 (2009)

Ponadto nowy algorytm przestrzeni logów do testowania płaskości i osadzania działa w skromnie wielomianowym czasie (oczywiście nieosiągalna modulo osiągalności)

Ref .: Samir Datta, Gautam Prakriya: Planarity Testing Revisited CoRR abs / 1101.2637: (2011)

Wreszcie, tutaj jest prosty problem z zabawkami, który ma algo przestrzeni logów o skromnym czasie działania (modulo undirected osiągalności), a mianowicie. Izomorfizm zewnętrzny.

— SamiD
źródło

1

Algorytm SSPD ma wartość

po znalezieniu osadzenia planarnego i wykorzystuje fakt, że istnieją ścieżki w logarytmicznym czasie, w przestrzeni dziennika do przejścia „najbardziej na lewo” i „najbardziej na prawo” z dowolnego wierzchołka do zlewu lub źródło dowolnego wierzchołka (nazwij te „zewnętrzne” ścieżki). Dla znalezienia drogi od

do

sprawdź, czy wierzchołki na zewnętrznych ścieżkach z U do umywalki są wzdłuż zewnętrznych ścieżkach od źródła do v.

O (n^{2})

$O(n^2)$

u

$u$

v

$v$

— Derrick Stolee

9

Ta odpowiedź jest bardziej problemem z zabawkami niż prawdziwym problemem badawczym.

Moim typowym przykładem algorytmu przestrzeni logów, który można przekazać znajomym programistów, jest następująca łamigłówka:

$n$

$O(\log n)$

Przesuwaj pierwszy wskaźnik na liście o jeden krok.
Przesuwaj drugi wskaźnik na liście o dwa kroki.
Jeśli którykolwiek ze wskaźników znajdzie koniec, zwróć false.
Jeśli węzły wskazują ten sam węzeł, zwróć wartość true.
W przeciwnym razie powtórz ponownie.

$n$ $n$

— Derrick Stolee
źródło

3

N C^{1}

$NC^1$

3

$O(n)$

$NC^1$

— Neel Krishnaswami
źródło

2

Ponieważ zmieniasz wykres, nie jest to algorytm przestrzeni logów, w którym taśma wejściowa musi być tylko do odczytu. Jest to interesujący algorytm sam w sobie.

— Derrick Stolee,