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

CC BY-SA 2.5
2010-10-23T23:46:46.597Z
good point, thanks :) On the second question - do you see any obvious flaws in the combinatorial approach to showing a thing like that?
gabgoh
CC BY-SA 2.5
2010-10-24T05:15:51.463Z
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).
Derrick Stolee
CC BY-SA 2.5
2010-10-24T06:52:59.897Z
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})$.
Kaveh
CC BY-SA 2.5
2010-10-24T15:29:42.240Z
Well, we don't.  Any improvement (even for specific $f$, such as $\log n$) would be a major breakthrough.
Derrick Stolee
CC BY-SA 2.5
2010-10-24T16:06:24.977Z
@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$.
Kaveh
CC BY-SA 2.5
2010-10-25T04:00:18.370Z
actually, taking a second look at these comments, it seems that Kaveh is correct, Karolina does not answer my question. However, seeing noone has shown me a paper demonstrating that it is tight, I am comfortable assuming it isn't.
gabgoh
CC BY-SA 2.5
2010-10-23T23:34:59.813Z
2010-10-23T23:34:59.813Z
Karolina Sołtys
<p>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 :)</p>

<p>For the latest result in this area, showing that Savitch's algorithm is optimal in some restricted model, see <a href="http://www.eccc.uni-trier.de/report/2009/142/">Aaron Potechin's FOCS paper</a>.</p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-02T03:09:22.467Z
2010-11-02T03:09:22.467Z
Boaz Barak
<p>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. </p>

<p>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 $&lt;2$ outgoing edges.</p>

<p>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.&nbsp;</p>

<cc.complexity-theory><space-bounded>
Tight Lower bounds on Savitch's theorem
gabgoh
# Tight Lower bounds on Savitch's theorem

(Asked by: username_0 on 2010-10-23)

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.

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

---

## 2 answers

### Answer by username_4 on 2010-11-02. Score: 31 | Accepted answer

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](http://www.eccc.uni-trier.de/report/2009/142/).

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.


---

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

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

> **Comments:**
> **username_0**: good point, thanks :) On the second question - do you see any obvious flaws in the combinatorial approach to showing a thing like that?  
> **username_2**: 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).  
> **username_3**: 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})$.  
> **username_2**: Well, we don't.  Any improvement (even for specific $f$, such as $\log n$) would be a major breakthrough.  
> **username_3**: @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$.  
> **username_0**: actually, taking a second look at these comments, it seems that Kaveh is correct, Karolina does not answer my question. However, seeing noone has shown me a paper demonstrating that it is tight, I am comfortable assuming it isn't.  

---

