26

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$.
Shiva Kintali
  • 10,578
  • 41
  • 74

3 Answers3

13

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.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
Derrick Stolee
  • 2,044
  • 1
  • 21
  • 34
10

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.

Derrick Stolee
  • 2,044
  • 1
  • 21
  • 34
6

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)

András Salamon
  • 19,000
  • 3
  • 64
  • 150
SamiD
  • 2,309
  • 17
  • 28
  • 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