Typically at the end of every ECE374 semester I give a small motivational speech to round things out and wish my children well. Because of paternity leave, this will be the first semester that I don’t get to give that speech. However, with this new blog set up, I figure it might be time to post my work online.

Walter Savitch was very famous computer scientist and unfortunately died a couple years ago at the age of 71. That is actually pretty young considering most of these guys live well into their 80s/90s (his advisor, Stephen Cook (of the Cook-Levin Theorem) is alive and well in the University of Toronto at the age of 81).

Walter Savitch.

Anyway, Walter Savitch is one of the fathers of computational space complexity and its relation to time. And in 1970 he proved Savitch’s theorem which basically states that any problem a non-deterministic Turing machine can solve, a deterministic Turing machine can solve in squared space.

The proof is actually not to hard to understand and Wikipedia does a great job of explaining it but essentially the proof consists of the following steps:

  • Relies on a known path-finding algorithm called STCON which can determine if there is a path between two vertices in \(O\left( \left( \text{log}n \right)^2 \right)\) space
  • Savitch argued that you can turn any nondeterministic computation that requires some \(f\left(n\right)\) space into a configuration graph
  • We know that the tape can decide \(x\) in \(f\left(n\right)\) space and therefore there are \(2^{O\left(f\left(n\right)\right)}\) configurations
  • And therefore the configuration graph has that many vertices
  • So we can use STCON to find a path between the initial configuration vertex and accepting configuration vertex in \(O\left(f\left(n\right)^2\right)\) time which is a quadratic increase in space requirement.

So that is the proof, but let’s return to the main idea. Basically a deterministic TM can solve any problem that a non-deterministic TM can solve with just a slight bit more space.

That is nuts.

You have this non-deterministic machine, this automata that operates pretty much on magic, and Walter Savitch showed that its less-fortunate, deterministic brother can solve the same problems with just a bit more space.

Mathematics and philosophy have always been beautifully intertwined. You can trace the idea of boolean expressions and logic (such as what we see in SAT) to Plato and so much of our biological preprogramming are simple algorithmic optimizations. So whenever I see theorems like this I like to muse on what they’re saying philosophically and in the case of Savitch’s theorem, I think the moral is quite poignant.

I’m sure everyone reading this has at one point felt like a deterministic machine among non-deterministic group, been stuck while everyone just seems to fly by. And man does that suck.

But here’s the good news, Savitch’s theorem proves that no matter how much fortune favors others, you can conquer the exact same challenges, all it will take is time.

And this isn’t me giving you a cliché’d motivational speech, this the result of all the logical knowledge we as human beings have and it is a result that is keeps coming up in all sorts of places.

The idea that whatever you do, just keep going appears in literature, politics, biology and so much else. As long as you do something for a long enough amount of time, the end result will probably be pretty spectacular.

So if there’s one thing that you should take away from these studies it should be this: DO SOMETHING. Just find a problem you like and start putting the hammer to the anvil. Doesn’t matter if there are people that are more talented or further ahead, as long as you keep working over a long enough time, you’ll get there. And that’s not me trying give you some hokey ego boost, that is what Walter Savitch proved mathematically and that is why his is my favorite theorem.

So get out there, work hard and as long as you keep going I know all of you achieve what you desire.