Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I am following "Introduction to the theory of computation" by Sipser.

My question is about relationship of different classes which is present in Chapter 8.2. The Class PSPACE.

$P \subseteq NP \subseteq PSPACE = NPSPACE \subseteq EXPTIME$

I am trying to understand why the the following part is true $NPSPACE \subseteq EXPTIME$.

The explanation from the textbook is following:

"For $f(x)\geq n$, a TM that uses $f(x)$ space can have at most $f(n)2^{O(f(n))}$ different configurations, by a simple generalization of the proof of the Lemma 5.8 on page 194. A TM computation that halts may not repeat a configuration. Therefore a TM that uses space $f(n)$ must run in time $f(n)2^{O(f(n))}$, so $NPSPACE \subseteq EXPTIME$"

I am trying to understand why it's true, why TM that uses $f(n)$ space must run in time $f(n)2^{O(f(n))}$. Let's try to reverseengeneer the formula: $n$ is the length of the input, 2 is the size of alphabet, $f(n)$ is the space that TM use on the second tape (operational tape) and $f(n) \geq n$, but how to explain what $O(f(n))$ means. Apparently, $2^{O(f(n))}$ expreses a configuration, so $O(f(n))$ must express union of transition function and alphabet, but actually it seems like I get it wrong. The most intriguing question why, in the end, $f(n)2^{O(f(n))}$ expressed in the terms of time, the transition from space to time is very vague for me.

I will very appreciate if someone could explain me this relationship.

share|improve this question
add comment

1 Answer

up vote 8 down vote accepted

The expression $f(n)2^{O(f(n))}$ is simply an upper bound for the number of all configurations a $f(n)$-space bounded TM can have. Here is how to count: We have $|\Gamma|^{f(n)}=2^{O(f(n)}$ different ways how to fill the work tape, and the head can be on $f(n)$ different positions. There is also a constant number of states where we can currently be, but this is hidden in the big-O in the exponent.

If a TM takes more than $f(n)2^{O(f(n))}$ steps, then it has to visit one configuration twice. Hence it cycles and cannot stop.

share|improve this answer
    
thank you very much for the answer, now it perfectly makes sense. –  com Nov 14 '12 at 7:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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