1
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ Problems in $\mathsf{SPACE}(n)$ need not be in $\mathsf{P}$! $\endgroup$ – Yuval Filmus Jun 24 '18 at 15:46
3
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$
  • 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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.