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 ( P ). Wiele znanych algorytmów przestrzeni logicznej (na przykład: nieukierowana łączność st, izomorfizm płaskiego wykresu) działa w O ( n k ), gdzie k jest niesamowicie duże.L.P.O(nk)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 k 10 . Nie ma nic specjalnego w 10. Patrząc na obecnie znane algorytmy przestrzeni logicznej, myślę, że k 10 jest wystarczająco interesujące.O(nk)k10k10
  • Aleliunas i in. pokazał, że nieukierowana łączność st jest w (losowy obszar logów). Czas działania ich algorytmu wynosi O ( n 3 ) . Czy istnieją naturalne problemy, które można rozwiązać jednocześnie w R L i czas liniowy (lub) w pobliżu czasie liniowym czyli O ( n log i n ) czas?RL.O(n3))RL.O(nlogjan)

Edycja: Aby uczynić rzeczy bardziej interesującymi, spójrzmy na problemy o twardości co najmniej .N.do1

Shiva Kintali
źródło
Czy istnieje analiza czasowa wersji logicznej twierdzenia Courcelle'a? eccc.uni-trier.de/report/2010/062
Hsien-Chih Chang 張顯 之

Odpowiedzi:

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(n2))

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 u do v 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(n2))uv
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(logn)

  • 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.

nn

Derrick Stolee
źródło
3
N.do1
3

O(n)

N.do1

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,