1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

Savitch's theorem shows that $\mathsf{NSPACE}(f(n)) \subseteq \mathsf{SPACE}(f(n)^2)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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