If I have some non-deterministic Turing machine $NDTM$ running some process $Q$ and I wish to simulate the same process $Q$ with a deterministic single-tape Turing machine $DTM$, there will of course be an exponential slowdown. However, what penalty can one expect in terms of space resources? Unless one has access to an $RNG$, presumably one has to keep track of which configurations one has already tried? Can we simulate the $NDTM$ with the $DTM$ using only polynomially more space?
1 Answer
$\begingroup$
$\endgroup$
Savitch's theorem shows that $\mathsf{NSPACE}(f(n)) \subseteq \mathsf{SPACE}(f(n)^2)$.
answered Dec 23, 2014 at 5:58