Problem Treewidth i NL vs L.

31

Łączność ST to problem polegający na określeniu, czy istnieje ukierunkowana ścieżka między dwoma wyróżnionymi wierzchołkami i t na ukierunkowanym wykresie G ( V , E ) . To, czy problem ten można rozwiązać w przestrzeni logów, jest od dawna otwartym problemem. Jest to tak zwany N l vs L problemu.stsol(V.,mi)N.L.L.

Jaka jest złożoność ST-Connectivity, gdy leżący u podstaw niekierowany wykres ograniczył szerokość.sol

Czy wiadomo, że jest trudny dla NL? Czy jest znana górna granica ?o(log2)n)

Shiva Kintali
źródło

Odpowiedzi:

25

Wygląda na to, że problemem jest L w [EJT10], a zatem L-zupełny przy redukowalności o [CM87]. Zobacz stronę 2 [EJT10]:NC1

Zastosowanie Twierdzenia I.3 do wzoru wyrażającego, że X jest prostą ścieżką od s do t, pokazuje, że problem { ( G , s , t ) |  tw ( G ) k , istnieje ścieżka od  s  do  t  w  G } leży w Lϕ(X)Xst{(sol,s,t) | tw(sol)k, jest ścieżka od s do t w sol}

W rzeczywistości ten wynik dotyczy wszystkich problemów na ograniczonych wykresach szerokości, które można sformułować w monadycznej logice drugiego rzędu w L.

[EJT10] Michael Elberfeld, Andreas Jakoby i Till Tantau. Wersje przestrzeni logicznej twierdzeń Bodlaendera i Courcelle. W materiałach 51. dorocznego sympozjum na temat podstaw informatyki (FOCS), strony 143–152, 2010.

[CM87] Stephen A. Cook, Pierre McKenzie: Problemy zakończone dla deterministycznej przestrzeni logarytmicznej. J. Algorytmy 8 (3): 385–394 (1987)

Michael Blondin
źródło