Intermediate problems between L and NL

Question

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$.

Answer 1

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.

Answer 2

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.

Answer 3

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)