29
$\begingroup$

First of all, I apologize in advance for any stupidity. I am by no means an expert on complexity theory (far from it! I am an undergraduate taking my first class in complexity theory) Here's my question. Now Savitch's Theorem states that $$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right)$$ Now I'm curious if if this lower bound was tight, i.e that is something along the lines of $\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^{1.9}\right)$ is not achievable.

It seems like something there should be a straightforward combinatorial argument to be made here - each node in the configuration graph for a Deterministic Turing machine has only one outgoing edge, while each node in the configuration graph of a Non-Deterministic Turing machine can have more than one outgoing edge. What Savitch's algorithm is doing is converting configuration graphs with any number outgoing edge to configuration graphs with $<2$ outgoing edges.

Since the configuration graph defines a unique TM (not sure about this), the combinatorial size of the latter is almost certainly larger than the former. This "difference" is perhaps a factor of $n^2$, perhaps less - I don't know. Of course, there are lots of little technical issues to be worked out, like how you need to make sure there are no loops and so forth, but my question is if this is a reasonable way to begun proving a thing like this. 

Improve this question
$\endgroup$

2 Answers 2

Reset to default
31
$\begingroup$

This is a well known open question. You will see in complexity theory many open questions for which you'd wonder how come no one managed to solve them. Part of the reason is that we need new people like you to help us solve them :)

For the latest result in this area, showing that Savitch's algorithm is optimal in some restricted model, see Aaron Potechin's FOCS paper.

Specifically, he starts from the nice observation that because the configuration graph of a deterministic TM has only one outgoing edge (after fixing the input), one can think of it as an undirected graph, and so the question becomes something like the following: given a directed graph $G$ of $n$ vertices with two special vertices $s,t$, if we map it to an $N$ vertex undirected graph $G'$ (also with special vertices $s',t'$) such that the existence of each edge in $G'$ depends on one edge in $G$ and there is a path from $s$ to $t$ in $G$ iff there's a path between $s'$ and $t'$ in $G'$, how much bigger $N$ has to be from $n$.

To show that Savitch's algorithm is optimal, one needs to show that $N$ has to be at least $2^{\Omega(\log^2 n)} = n^{\Omega(\log n)}$. To show $L\neq NL$, it suffices to show the weaker bound that $N > n^c$ for every constant $c$. I'm pretty sure that even $N > n^{10}$ is not known, though perhaps something like $N \geq n^2$ is known for some not so interesting reasons.

Improve this answer
$\endgroup$
21
$\begingroup$

I think we don't know whether this is tight. Otherwise we would know that $L \neq NL$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ good point, thanks :) On the second question - do you see any obvious flaws in the combinatorial approach to showing a thing like that? $\endgroup$
    – gabgoh
    Commented Oct 23, 2010 at 23:46
  • 2
    $\begingroup$ Savitch's theorem is a specific algorithm for simulating a non-deterministic f(n)-space algorithm by using divide-and-conquer with an O(f(n)) depth (giving f(n)^2). Proving lower bounds involves showing that ALL algorithms that use less space fail on some inputs. This is the reason L = NL is hard (and P = NP is hard). $\endgroup$
    – Derrick Stolee
    Commented Oct 24, 2010 at 5:15
  • 1
    $\begingroup$ We don't know if it is tight in the sense that we don't know that 2 is the best one can do, but that doesn't meant that we don't know $NSpace(f(n)) \subseteq DSpace((f(n))^{1.9})$. $\endgroup$
    – Kaveh
    Commented Oct 24, 2010 at 6:52
  • 1
    $\begingroup$ Well, we don't. Any improvement (even for specific $f$, such as $\log n$) would be a major breakthrough. $\endgroup$
    – Derrick Stolee
    Commented Oct 24, 2010 at 15:29
  • 2
    $\begingroup$ @Derrick Stolee: You are missing the point of my comment. Only knowing positive answer would imply that $L \neq NL$, Karolina's argument does not give any evidence for difficulty of knowing a negative answer, i.e. knwoing $NSpace(f(n)) \subseteq DSpace((f(n))^{1.9})$ doesn't seem to help with $L$ vs $NL$. $\endgroup$
    – Kaveh
    Commented Oct 24, 2010 at 16:06

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.