Problemy pośrednie między L i NL

Jest dobrze wiadomo, że skierowane st-łączność jest -Complete. Przełom wynik Reingold wykazała, że nieukierunkowane st-łączność jest w L . Płaskie skierowane st-łączności jest znany w U L ∩ C O U L . Cho Huynh zdefiniowano sparametryzowanego problemu plecakowego i wykazywał hierarchię problemów między L i N l .$NL$$L$$UL \cap coUL$$L$$NL$

Szukam więcej problemów, które są pośrednie między i N L, tj. Problemów, które są:$L$$NL$

• Wiadomo, że w , ale nie jest znana (lub raczej) jest N L -Complete i$NL$$NL$
• Wiadomo, że -hard ale wiadomo, że w L .$L$$L$

Problem RL kompletne osiągalności w skierowanych wykresów wielomianowej mieszania w czasie (wskazanym Reingold, Trevisan i Vadhan w pseudolosowy wchodzi w zwykłych digrafach i problem RL wobec L ) w przestrzeń (patrz BPHSPACE ( S ) ⊆ dSPACE ( S 3 / 2 ) przez Saks Zhou ), która jest ściśle między L i Savitch na związane na NI o ( log 2 n ) przestrzeni.$\log^{3/2}(n)$$\text{BPHSPACE}(S) \subseteq \text{DSPACE}(S^{3/2})$$O(\log^2 n)$

$O(\log^2 n / \log\log n)$$\text{RUSPACE}(\log n) \subseteq \text{DSPACE}(\log^2 n/\log\log n)$

$\mathsf{UL}$$\mathsf{UL} \cap \mathsf{coUL}$$\mathsf{L}$

Ref: Samir Datta, Raghav Kulkarni, Raghunath Tewari: Idealne dopasowanie na dwustronnych wykresach planarnych jest w UL. Electronic Colloquium on Computational Complexity (ECCC) 17: 201 (2010)