3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ thank you very much for the answer, now it perfectly makes sense. $\endgroup$
    – com
    Nov 14, 2012 at 7:20
  • $\begingroup$ Nice answer I just could not understand the part where you said : "but this is hidden in the big-$O$ in the exponent". Can you explain to me why that is so? In other words, I don't understand why the TM cannot have more than $2^{O(f(n))}$ states. $\endgroup$
    – User Not Found
    Jul 2, 2017 at 14:33
  • 1
    $\begingroup$ Assume that $c$ is a constant, then $c=2^{\log c}$. Thus, $c\cdot 2^{O(f(n))}$ is equivalent to $2^{\log c + O(f(n))}$ . But $\log c $ is a constant as well and so $2^{\log c + O(f(n))}= 2^{ O(f(n))}$. $\endgroup$
    – A.Schulz
    Jul 3, 2017 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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