<p>The RL-complete problem of reachability in directed graphs with polynomial mixing-time (shown by Reingold, Trevisan, and Vadhan in <a href="http://portal.acm.org/citation.cfm?id=1132583">Pseudorandom walks on regular digraphs and the RL vs. L problem</a>) is in $\log^{3/2}(n)$ space (see $\text{BPHSPACE}(S) \subseteq \text{DSPACE}(S^{3/2})$ by <a href="http://dx.doi.org/10.1006/jcss.1998.1616">Saks and Zhou</a>), which is strictly between L and Savitch's bound on NL of $O(\log^2 n)$ space.</p>

CC BY-SA 2.5
2010-09-21T05:20:22.833Z
2010-09-21T05:31:57.663Z
2010-09-21T05:31:57.663Z
Derrick Stolee
<p>The RUL-complete problem of reachability in mangroves can be decided in $O(\log^2 n / \log\log n)$ space (<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.5808">Allender, Lange</a>, $\text{RUSPACE}(\log n) \subseteq \text{DSPACE}(\log^2 n/\log\log n)$).  A <em>mangrove</em> is a directed graph where there is at most one path between any two vertices.</p>

CC BY-SA 2.5
2010-09-21T05:46:31.890Z
See also: Lange, "An Unambiguous Class Possessing a Complete Set" STACS '97.
Derrick Stolee
CC BY-SA 2.5
2010-09-21T05:45:21.847Z
2010-09-21T05:45:21.847Z
Derrick Stolee
<p>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.</p>

<p>Ref: Samir Datta, Raghav Kulkarni, Raghunath Tewari: Perfect Matching in Bipartite Planar Graphs is in UL. Electronic Colloquium on Computational Complexity (ECCC) <a href="http://eccc.hpi-web.de/report/2010/201/" rel="nofollow">17: 201</a> (2010)</p>

CC BY-SA 3.0
2011-07-18T19:43:02.197Z
I guess I should be a bit embarrassed about the stale answer - but just for the sake of completeness.
SamiD
CC BY-SA 3.0
2011-07-18T19:40:51.777Z
2016-05-01T10:57:20.947Z
2016-05-01T10:57:20.947Z
SamiD
<p>It is well-known that <a href="http://en.wikipedia.org/wiki/St-connectivity">directed st-connectivity</a> is $NL$-complete. Reingold's breakthrough result showed that <a href="http://en.wikipedia.org/wiki/SL_%28complexity%29">undirected st-connectivity</a> is in $L$. <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.125.8061">Planar directed st-connectivity</a> is known to be in $UL \cap coUL$. <a href="http://portal.acm.org/citation.cfm?id=57031.57034">Cho and Huynh</a> defined a parametrized knapsack problem and exhibited a hierarchy of problems between $L$ and $NL$. </p>

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

<ul>
<li>known to be in $NL$ but not known (or unlikely) to be $NL$-complete and</li>
<li>known to be $L$-hard but not known to be in $L$.</li>
</ul>

<cc.complexity-theory><space-bounded>
Intermediate problems between L and NL
Shiva Kintali
# Intermediate problems between L and NL

(Asked by: username_0 on 2010-09-21)

It is well-known that [directed st-connectivity](http://en.wikipedia.org/wiki/St-connectivity) is $NL$-complete. Reingold's breakthrough result showed that [undirected st-connectivity](http://en.wikipedia.org/wiki/SL_%28complexity%29) is in $L$. [Planar directed st-connectivity](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.125.8061) is known to be in $UL \cap coUL$. [Cho and Huynh](http://portal.acm.org/citation.cfm?id=57031.57034) 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$.

**Tags:** cc.complexity-theory, space-bounded


---

## 3 answers

### Answer by username_1 on 2010-09-21. Score: 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](http://portal.acm.org/citation.cfm?id=1132583)) is in $\log^{3/2}(n)$ space (see $\text{BPHSPACE}(S) \subseteq \text{DSPACE}(S^{3/2})$ by [Saks and Zhou](http://dx.doi.org/10.1006/jcss.1998.1616)), which is strictly between L and Savitch's bound on NL of $O(\log^2 n)$ space.


---

### Answer by username_1 on 2010-09-21. Score: 10

The RUL-complete problem of reachability in mangroves can be decided in $O(\log^2 n / \log\log n)$ space ([Allender, Lange](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.5808), $\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.

> **Comments:**
> **username_1**: See also: Lange, "An Unambiguous Class Possessing a Complete Set" STACS '97.  

---

### Answer by username_2 on 2011-07-18. Score: 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](http://eccc.hpi-web.de/report/2010/201/) (2010)

> **Comments:**
> **username_2**: I guess I should be a bit embarrassed about the stale answer - but just for the sake of completeness.  

---

