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
    Commented 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
    Commented 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
    Commented 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
    Commented 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 張顯之
    Commented 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
    Commented Sep 26, 2010 at 8:22
  • $\begingroup$ @ShivaKintali What do you mean by intermediate problems? $\endgroup$
    – Turbo
    Commented Nov 25, 2022 at 21:16
  • 1
    $\begingroup$ @Turbo Intermediate problems are those whose complexity lies between L and NL. $\endgroup$
    – Shiva Kintali
    Commented Nov 27, 2022 at 0:54

Your Answer

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

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