It is well-known that directed st-connectivity is $NL$-complete. Reingold's breakthrough result showed that undirected st-connectivity is in $L$. Planar directed st-connectivity is known to be in $UL \cap coUL$. Cho and Huynh defined a parametrized knapsack problem and exhibited a hierarchy of problems between $L$ and $NL$.

I am looking for more problems that are intermediate between $L$ and $NL$ i.e., problems that are :

  • known to be in $NL$ but not known (or unlikely) to be $NL$-complete and
  • known to be $L$-hard but not known to be in $L$.

The RL-complete problem of reachability in directed graphs with polynomial mixing-time (shown by Reingold, Trevisan, and Vadhan in Pseudorandom walks on regular digraphs and the RL vs. L problem) is in $\log^{3/2}(n)$ space (see $\text{BPHSPACE}(S) \subseteq \text{DSPACE}(S^{3/2})$ by Saks and Zhou), which is strictly between L and Savitch's bound on NL of $O(\log^2 n)$ space.

The RUL-complete problem of reachability in mangroves can be decided in $O(\log^2 n / \log\log n)$ space (Allender, Lange, $\text{RUSPACE}(\log n) \subseteq \text{DSPACE}(\log^2 n/\log\log n)$). A mangrove is a directed graph where there is at most one path between any two vertices.

  • 1
    See also: Lange, "An Unambiguous Class Possessing a Complete Set" STACS '97. – Derrick Stolee Sep 21 '10 at 5:46

Bipartite Planar Perfect Matching is known to be in $\mathsf{UL}$ (though not in $\mathsf{UL} \cap \mathsf{coUL}$). Since Planar Reachability reduces to it, it is $\mathsf{L}$-hard.

Ref: Samir Datta, Raghav Kulkarni, Raghunath Tewari: Perfect Matching in Bipartite Planar Graphs is in UL. Electronic Colloquium on Computational Complexity (ECCC) 17: 201 (2010)

  • I guess I should be a bit embarrassed about the stale answer - but just for the sake of completeness. – SamiD Jul 18 '11 at 19:43

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.