patternMinor
Show that NP is not equal to SPACE(n)
Viewed 0 times
showspaceequalthatnot
Problem
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...
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...
Solution
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:
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)$.
Your argument, as I understand it, is roughly as follows:
- Every machine in $\mathsf{SPACE}(n)$ runs in at most exponential time.
- 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)$.
Context
StackExchange Computer Science Q#93434, answer score: 7
Revisions (0)
No revisions yet.