# Proving that NPSPACE $\subseteq$ EXPTIME

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.

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.
• 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. – User Not Found Jul 2 '17 at 14:33
• 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))}$. – A.Schulz Jul 3 '17 at 6:15