Confusion about NP vs. LINSPACE

Question

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.

Answer 1

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.