Show that NP is not equal to SPACE(n)

Question

I want to show that $\text{NP} \neq \text{SPACE}(n)$ and tried it like this:

Let $L$ be in $\text{SPACE}(n)$ so there is a deterministic $k$-tape TM which decides $L$ in polynomial time. Let's consider a binary alphabet. There are $2^{kn}$ possible strings on the working tapes so for an input of length $n$ the TM can be in $2^{kn} \cdot k \cdot n \cdot |Q|$ different configurations where $Q$ is the finite state set.

Since the TM is deterministic and decides $L$ no configuration can be visited twice (otherwise we would be in an infinite loop). So $2^{kn} \cdot k \cdot n \cdot |Q|$ is also an upper bound for the runtime of the TM which is exponential and therefore not in $NP$.

Is this argumentation enough? I found this answer on the internet and now I'm confused because it looks so much more complexive but also comprehensibly...

Answer 1

In order to prove that $\mathsf{SPACE}(n) \not\subseteq \mathsf{NP}$, you need to identify a language in $\mathsf{SPACE}(n)$ which is not in $\mathsf{NP}$. Not every language in $\mathsf{SPACE}(n)$ would work — for example, every regular language is in $\mathsf{SPACE}(n)$, and all of these are also in $\mathsf{NP}$.

Your argument, as I understand it, is roughly as follows:

1. Every machine in $\mathsf{SPACE}(n)$ runs in at most exponential time.
2. Hence every such machine is not in $\mathsf{NP}$.

The second conclusion is not correct, since exponential time is only an upper bound. For example, a DFA uses constant space and does run in polynomial time.

Worse, even if some machine in $\mathsf{SPACE}(n)$ does run in exponential time, it could be that there exists another machine accepting the same language that runs in polynomial time — especially if we are allowed to use nondeterminism. As an example, it is suspected that $\mathsf{SAT}$ (which is in $\mathsf{SPACE}(n)$) requires exponential time, but it does belong to $\mathsf{NP}$.

The proof outlined in your link is not too hard, given the space hierarchy theorem. This theorem gives you a language $L$ which is in $\mathsf{SPACE}(n^2)$ but not in $\mathsf{SPACE}(n)$. The padded language $L' = \{ 1^{|x|^2}0x : x \in L \}$ does lie in $\mathsf{SPACE}(n)$ (why?), and so if the latter is equal to $\mathsf{NP}$, it follows that $L' \in \mathsf{NP}$. However, $L$ polytime reduces to $L'$, and so it would follow that $L \in \mathsf{NP}$ as well, contradicting $L \notin \mathsf{SPACE}(n)$.

Answer 2

• Problems in $\mathrm{NP}$ use a non-deterministic TM for running in polynomial time. So it's not a proof of not being in $\mathrm{NP}$ that a TM runs in exponential time on a deterministic TM.
• There is no proof for the existence of a TM which satisfies the upper bound.