<p>The last complexity conference showed some progress on this question. <a href="https://faculty.math.illinois.edu/%7Estolee/Papers/SBV10-LogspacePlanarDAGs.pdf" rel="nofollow noreferrer" title="doi:10.1109/CCC.2010.36">Reachability in planar DAGs with <span class="math-container">$O(\log n)$</span> sources can be solved in <span class="math-container">$O(\log n)$</span> space</a>.</p>
<p>Here is also a recent survey by Allender: <a href="https://doi.org/10.1007/978-3-540-73001-9_3" rel="nofollow noreferrer">&quot;Reachability Problems: An Update&quot;</a></p>

CC BY-SA 4.0
2022-11-25T21:16:46.840Z
@ShivaKintali What do you mean by intermediate problems?
Turbo
CC BY-SA 4.0
2022-11-27T00:54:00.973Z
@Turbo Intermediate problems are those whose complexity lies between L and NL.
Shiva Kintali
CC BY-SA 2.5
2010-09-26T08:22:20.287Z
It appears that none of the "intermediate" problems (except RL) are known to be in SC^2.
Shiva Kintali
CC BY-SA 4.0
2010-09-25T20:05:51.867Z
2022-11-29T08:10:47.967Z
2022-11-29T08:10:47.967Z
Ryan Williams
<p>There are two related complexity classes in $\text{NL}$ which are also in $\text{LogDCFL}$, which puts them in $\text{SC}^2$ (by <a href="http://portal.acm.org/citation.cfm?id=800135.804426" rel="nofollow noreferrer">Cook</a>).  </p>

<ul>
<li>The first is $\text{RUL}$, for "Reach-Unambiguous Log-space" which has reachability in mangroves (graphs where every pair of vertices has at most one directed path between them) as a complete problem.  This class has been <a href="https://cstheory.stackexchange.com/questions/1535/intermediate-problems-between-l-and-nl/1538#1538">discussed before</a>.</li>
<li>The second is $\text{ReachFewL}$, which has reachability complete for graphs with at most a polynomial number of paths between any pair of vertices. </li>
</ul>

<p>Performing depth-first search on these graphs using a stack has a guarantee that it will take polynomial time, so these classes are in $\text{LogDCFL} \subseteq \text{SC}^2$.</p>

CC BY-SA 2.5
2011-02-24T00:52:55.703Z
The reference for RUL in SC$^2$ is given in Klaus-Jörn Lange, "An unambiguous class possessing a complete set" STACS ’97.
Derrick Stolee
CC BY-SA 3.0
2011-08-14T22:31:14.990Z
News from COCOON'11: Now $\mathsf{ReachFewL}$ is [equal to](http://eccc.hpi-web.de/report/2011/060/) $\mathsf{ReachUL}$. Woohoo!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-10-07T22:52:32.773Z
@Derrick : Please add the references showing that these problems are in LogDCFL.
Shiva Kintali
CC BY-SA 2.5
2010-10-07T23:40:30.057Z
@Shiva: I thought the last paragraph was an argument that these problems can be recognized by a deterministic pushdown automaton determined by the graph?
András Salamon
CC BY-SA 2.5
2010-10-08T01:20:17.100Z
@András : Yes. I am just curious about the references. They might have connections to other problems and other insights.
Shiva Kintali
CC BY-SA 2.5
2010-10-08T03:33:53.923Z
I'm not sure about an original reference for showing they are in LogDCFL, because the proof is one line.
Derrick Stolee
CC BY-SA 2.5
2010-10-08T21:53:15.787Z
@Derrick : Thanks. So there are problems in the intersection of NL and LogDCFL that are not known to be in Logspace. Interesting !!
Shiva Kintali
CC BY-SA 2.5
2010-10-08T21:55:14.377Z
Yes, very interesting.  Again, mangroves have the (log log n) factor of space efficiency over the savitch bound, but I don't know of a similar bound for ReachFewL graphs.
Derrick Stolee
CC BY-SA 2.5
2010-10-07T22:23:37.573Z
2010-10-08T03:53:13.250Z
2017-04-13T12:32:28.080Z
Derrick Stolee
<p><a href="http://en.wikipedia.org/wiki/Savitch%27s_theorem">Savitch</a> gave a deterministic algorithm to solve <a href="http://en.wikipedia.org/wiki/St-connectivity">st-connectivity</a> using $O({\log}^2{n})$ space, implying $NL \subseteq DSPACE({\log}^2{n})$. Savitch’s algorithm runs in time $2^{O({\log}^2{n})}$. It is a major open problem whether st-connectivity can be solved by a deterministic algorithm in polynomial time and $O({\log}^2{n})$ space i.e., whether $NL \subseteq SC^2$. $RL$, which lies between $L$ and $NL$, is <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2997">known</a> be in $SC^2$. Hence reachability in directed graphs with polynomial mixing-time is in $SC^2$.</p>

<p>I am looking for special cases of st-connectivity (that are not known to be in $L$) that have $SC^2$ algorithms. Is anything known about planar graphs, planar DAGs ?
 Note that st-connectivity in DAGs remains NL-complete.</p>

<cc.complexity-theory><space-bounded>
SC^2 algorithms for st-connectivity
Shiva Kintali
# SC^2 algorithms for st-connectivity

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

[Savitch](http://en.wikipedia.org/wiki/Savitch%27s_theorem) gave a deterministic algorithm to solve [st-connectivity](http://en.wikipedia.org/wiki/St-connectivity) using $O({\log}^2{n})$ space, implying $NL \subseteq DSPACE({\log}^2{n})$. Savitch’s algorithm runs in time $2^{O({\log}^2{n})}$. It is a major open problem whether st-connectivity can be solved by a deterministic algorithm in polynomial time and $O({\log}^2{n})$ space i.e., whether $NL \subseteq SC^2$. $RL$, which lies between $L$ and $NL$, is [known](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2997) be in $SC^2$. Hence reachability in directed graphs with polynomial mixing-time is in $SC^2$.

I am looking for special cases of st-connectivity (that are not known to be in $L$) that have $SC^2$ algorithms. Is anything known about planar graphs, planar DAGs ?
Note that st-connectivity in DAGs remains NL-complete.

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


---

## 2 answers

### Answer by username_3 on 2010-10-07. Score: 12 | Accepted answer

There are two related complexity classes in $\text{NL}$ which are also in $\text{LogDCFL}$, which puts them in $\text{SC}^2$ (by [Cook](http://portal.acm.org/citation.cfm?id=800135.804426)).

* The first is $\text{RUL}$, for "Reach-Unambiguous Log-space" which has reachability in mangroves (graphs where every pair of vertices has at most one directed path between them) as a complete problem. This class has been [discussed before](https://cstheory.stackexchange.com/questions/1535/intermediate-problems-between-l-and-nl/1538#1538).
* The second is $\text{ReachFewL}$, which has reachability complete for graphs with at most a polynomial number of paths between any pair of vertices.

Performing depth-first search on these graphs using a stack has a guarantee that it will take polynomial time, so these classes are in $\text{LogDCFL} \subseteq \text{SC}^2$.

> **Comments:**
> **username_0**: @Derrick : Please add the references showing that these problems are in LogDCFL.  
> **username_5**: @Shiva: I thought the last paragraph was an argument that these problems can be recognized by a deterministic pushdown automaton determined by the graph?  
> **username_0**: @András : Yes. I am just curious about the references. They might have connections to other problems and other insights.  
> **username_3**: I'm not sure about an original reference for showing they are in LogDCFL, because the proof is one line.  
> **username_0**: @Derrick : Thanks. So there are problems in the intersection of NL and LogDCFL that are not known to be in Logspace. Interesting !!  
> **username_3**: Yes, very interesting.  Again, mangroves have the (log log n) factor of space efficiency over the savitch bound, but I don't know of a similar bound for ReachFewL graphs.  
> **username_3**: The reference for RUL in SC$^2$ is given in Klaus-Jörn Lange, "An unambiguous class possessing a complete set" STACS ’97.  
> **username_4**: News from COCOON'11: Now $\mathsf{ReachFewL}$ is [equal to](http://eccc.hpi-web.de/report/2011/060/) $\mathsf{ReachUL}$. Woohoo!  

---

### Answer by username_1 on 2010-09-25. Score: 12

The last complexity conference showed some progress on this question. [Reachability in planar DAGs with $O(\log n)$ sources can be solved in $O(\log n)$ space](https://faculty.math.illinois.edu/%7Estolee/Papers/SBV10-LogspacePlanarDAGs.pdf "doi:10.1109/CCC.2010.36").

Here is also a recent survey by Allender: ["Reachability Problems: An Update"](https://doi.org/10.1007/978-3-540-73001-9_3)

> **Comments:**
> **username_0**: It appears that none of the "intermediate" problems (except RL) are known to be in SC^2.  
> **username_2**: @ShivaKintali What do you mean by intermediate problems?  
> **username_0**: @username_2 Intermediate problems are those whose complexity lies between L and NL.  

---

