Problem Treewidth i NL vs L.

Łą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.$s$$t$$G(V,E)$$NL$$L$

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

Czy wiadomo, że jest trudny dla NL? Czy jest znana górna granica ?$o({\log}^2n)$

Wygląda na to, że problemem jest L w [EJT10], a zatem L-zupełny przy redukowalności o [CM87]. Zobacz stronę 2 [EJT10]:$\text{NC}^1$

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$\phi(X)$$X$$s$$t$$\{(G,s,t) \text{ } | \text{ tw$(G) \leq k$, there is a path from $s$ to $t$ in $G$}\}$

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)