Treewidth dan Masalah NL vs L.

ST-Konektivitas adalah masalah menentukan apakah ada jalur terarah antara dua simpul dan t dalam grafik berarah G ( V , E ) . Apakah masalah ini dapat diselesaikan di logspace, adalah masalah terbuka yang sudah lama ada. Ini disebut N L vs L masalah.$s$$t$$G(V,E)$$NL$$L$

Apa kompleksitas ST-Connectivity, ketika grafik tidak berarah yang mendasari telah membatasi treewidth.$G$

Apakah diketahui keras-NL? Apakah ada batas atas dikenal?$o({\log}^2n)$

Tampaknya masalahnya adalah dalam L oleh [EJT10] dan dengan demikian L-lengkap di bawah reducibilitas oleh [CM87]. Lihat halaman 2 dari [EJT10]:$\text{NC}^1$

Menerapkan Teorema I.3 ke rumus menyatakan bahwa X adalah jalur sederhana dari s ke t menunjukkan bahwa masalah { ( G , s , t ) |  tw ( G ) ≤ k , ada jalur dari  s  ke  t  di  G } terletak di 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$}\}$

Sebenarnya hasil ini berlaku untuk semua masalah pada grafik treewidth terbatas yang dapat dirumuskan dalam logika orde dua monadik dalam L.

[EJT10] Michael Elberfeld, Andreas Jakoby, dan Till Tantau. Versi logspace dari teorema Bodlaender dan Courcelle. Dalam Prosiding Simposium Tahunan ke-51 tentang Yayasan Ilmu Komputer (FOCS), halaman 143–152, 2010.

[CM87] Stephen A. Cook, Pierre McKenzie: Masalah Lengkap untuk Ruang Logaritma Deterministik. J. Algoritma 8 (3): 385-394 (1987)