17
$\begingroup$

Savitch gave a deterministic algorithm to solve 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 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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\begingroup$

There are two related complexity classes in $\text{NL}$ which are also in $\text{LogDCFL}$, which puts them in $\text{SC}^2$ (by Cook).

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ @Derrick : Please add the references showing that these problems are in LogDCFL. $\endgroup$
    – Shiva Kintali
    Oct 7, 2010 at 22:52
  • 1
    $\begingroup$ @Derrick : Thanks. So there are problems in the intersection of NL and LogDCFL that are not known to be in Logspace. Interesting !! $\endgroup$
    – Shiva Kintali
    Oct 8, 2010 at 21:53
  • 2
    $\begingroup$ 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. $\endgroup$
    – Derrick Stolee
    Oct 8, 2010 at 21:55
  • 1
    $\begingroup$ The reference for RUL in SC$^2$ is given in Klaus-Jörn Lange, "An unambiguous class possessing a complete set" STACS ’97. $\endgroup$
    – Derrick Stolee
    Feb 24, 2011 at 0:52
  • 2
    $\begingroup$ News from COCOON'11: Now $\mathsf{ReachFewL}$ is equal to $\mathsf{ReachUL}$. Woohoo! $\endgroup$
    – Hsien-Chih Chang 張顯之
    Aug 14, 2011 at 22:31
12
$\begingroup$

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.

Here is also a recent survey by Allender: "Reachability Problems: An Update"

Improve this answer
$\endgroup$
3
  • $\begingroup$ It appears that none of the "intermediate" problems (except RL) are known to be in SC^2. $\endgroup$
    – Shiva Kintali
    Sep 26, 2010 at 8:22
  • $\begingroup$ @ShivaKintali What do you mean by intermediate problems? $\endgroup$
    – Turbo
    Nov 25, 2022 at 21:16
  • 1
    $\begingroup$ @Turbo Intermediate problems are those whose complexity lies between L and NL. $\endgroup$
    – Shiva Kintali
    Nov 27, 2022 at 0:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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