# Confusion about NP vs. LINSPACE

I am working through Sipser, and have come accross the following claim, "any $$f(n)$$ space bounded Turing machine also runs in time $$2^{O(f(n))}$$", which can be proven by looking at the upper bound on the number of configurations a Turing machine that uses space $$f(n)$$ can take. An implication of this claim is that a $$f(n) = n$$ space bounded Turing machine runs in time $$2^{O(n)}$$, and hence I take it this means that any Turing machine running in time $$2^{O(n)}$$ is a $$O(n)$$ space Turing machine.

Now there is an excersise I am doing that asks that you prove that $$NP \not= SPACE(n) = LINSPACE$$ (see problem 4). Using the logic above from Sipser, I am arguing that if $$NP \not\subseteq SPACE(n)$$ then there is an NP-complete problem $$A$$ not in $$TIME(2^{n}$$). But what would such a problem $$A$$ look like? I take it that it would need to be a problem in say $$TIME(n!)$$ or $$TIME(n^n)$$ (i.e. a language decidable by a superexponential time Turing machine)?

Moreover, as stated in the link, it is unknown if $$NP \subseteq SPACE(n)$$ or $$SPACE(n) \subseteq NP$$. So is the reason why we cannot prove $$NP \not\subseteq SPACE(n)$$ for example because all the known NP-complete problems are in $$TIME(2^n)$$? For example in subset-sum for a set of $$n$$ integers there are $$2^n$$ possible subsets, and indeed all NP-complete problems are similar.

The relationships between time and space on which you are relying are not correct. In particular, it is true that

$$\forall \ \mathrm{T}(n) \ \mathrm{DSPACE}_{\mathrm{TM}}(\mathrm{T}(n)) \subseteq \mathrm{DTIME}_{\mathrm{TM}}\left(\mathrm{T}(n) 2^{O(T(n))}\right.)$$

and

$$\forall \ \mathrm{T}(n) \ \mathrm{NSPACE}_{\mathrm{TM}}(\mathrm{T}(n)) \subseteq \mathrm{NTIME}_{\mathrm{TM}}\left(\mathrm{T}(n) 2^{O(T(n))}\right.)$$

This is because a TM that uses $$T(n)$$ space can have at most $$T(n)\cdot 2^{O(T(n))}$$ different configurations. However, the converse is not true:

$$\forall\ \ \mathrm{T}(n) \ \mathrm{DTIME}_{\mathrm{TM}}(\mathrm{T}(n)) \subseteq \mathrm{DSPACE}_{\mathrm{TM}}(\mathrm{T}(n))$$

and

$$\forall \ T(n)\ NT I M E_{T M}(T(n)) \subseteq \text { NSPACE }_{T M}(T(n))$$.

Indeed, at each step, a $$k$$ tapes TM can write on at most $$k = O(1)$$ previously unwritten cells; therefore, a TM operating in time $$T(n)$$ can use at most $$T(n)$$ space.

Having said that, you need to show that $$NP$$ and $$SPACE(n)$$ are different sets. For this you may use the well-known fact that $$NP$$ is closed with regard to log-space reductions (i.e., the reductions used to show that a problem in $$P$$ is a $$P-$$Complete problem) and prove that, instead, $$SPACE(n)$$ is not closed with regard to log-space reductions. For this, you can use the Space Hierarchy Theorem. For the details, please see this answer by @YuvalFilmus.