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{ ( G , s , t ) | tw ( G ) ≤ k , istnieje ścieżka od s do t w 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)