Ł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.
- 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.
- 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?
Edycja: Aby uczynić rzeczy bardziej interesującymi, spójrzmy na problemy o twardości co najmniej .
cc.complexity-theory
space-bounded
space-time-tradeoff
Shiva Kintali
źródło
źródło
Odpowiedzi:
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.
źródło
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:
źródło
źródło