World's most popular travel blog for travel bloggers.

Space penalties for the simulation of a non-deterministic Turing machine by a single-tape deterministic Turing machine

, , No Comments
Problem Detail: 

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?

Asked By : CRJ
Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback