27

I've seen that P != LINSPACE (by which I mean SPACE(n)), but that we don't know if one is a subset of the other.

I assume that means that the proof must not involve showing a problem that's in one class but not the other, so how else would you go about proving it?

Thanks!

wjomlex
  • 503

4 Answers4

53

Suppose by contradiction that P=SPACE(n). Then there exists an algorithm to simulate an n-space Turing machine in (say) nc time, for some constant c. But this means that there exists an algorithm to simulate an n2-space Turing machine in n2c time. Therefore SPACE(n2) is also contained in P. So

P = SPACE(n) = SPACE(n2).

But SPACE(n) = SPACE(n2) contradicts the Space Hierarchy Theorem. QED

(Notice that in this proof, we showed neither that P is not contained in SPACE(n), nor that SPACE(n) is not contained in P! We only showed that one or the other must be true, by using the different closure properties of polynomial time and linear space. It's conjectured that P and SPACE(n) are incomparable.)

Scott Aaronson
  • 9,743
  • 4
    This proof works also for showing that NP is not equal to SPACE(n). – Henry Yuen Oct 01 '10 at 16:54
  • 3
    Or, indeed, in SPACE(n^k) for fixed k. – Charles Oct 01 '10 at 19:39
  • It is not clear to me, whether the "algorithm" in the second sentence is meant to be universal, or whether each n-space machine translates to a different PTIME machine. But then there's a bigger jump. I can see how then to simulate any $n^2$-space machine in time $n^{c}.2^{O(n)}+c$, but not in $n^{2c}$-time. Can you please elaborate that step or cite? – Jirka Hanika Mar 16 '12 at 21:35
  • 3
    Jirka: Sorry, just saw your comment! All you need to do is feed your $n^2$-space machine to your algorithm for $n$-space machines. But don't tell the algorithm you're giving it an $n^2$-space machine! Just tell it you're giving it an $N$-space machine, but choose $N$ so that it happens to equal $n^2$. :-) – Scott Aaronson Nov 23 '13 at 07:03
  • 1
    Taken literally, the second sentence of this answer is plain wrong. The easiest way to avoid plain wrong sentences would be to explicitly indicate the dependence on the Turing machine $M$: "Then there exists an algorithm to simulate an $n$-space Turing machine $M$ in (say) $n^{c(M)}$ time, for some constant $c(M)$. But this means that there exists an algorithm to simulate an $n^2$-space Turing machine $M'$ in $(n^2)^{c'(M')}$ time." Alternatively, one can distinguish explicitly between complexity classes and languages, like done in the other answers. – Thomas Klimpel Mar 16 '14 at 15:53
  • @ScottAaronson ping (see also the two other answers) – Thomas Klimpel Apr 12 '14 at 17:00
10

I think I spotted a problem with the above proof by Scott. If P=SPACE($n$) implied that there's an algorithm to simulate an n-space Turing machine in (say) $n^c$ time, for some constant $c$, it would also imply that there's an algorithm in $n^c$ time to simulate all polynomial time Turing machines, and that P=TIME($n^c$), which contradicts the Time Hierarchy Theorem. But this problem can be fixed, of course:

Suppose that P=SPACE($n$). For contradiction with the Space Hierarchy Theorem, we'd like to show that every language in SPACE($n^2$) can be reduced in polynomial time to SPACE($n$). We will do this using the padding argument.

Let $L$ ∈ SPACE($n^2$), $M$ a Turing machine with space complexity $n^2$ for the language $L$. Let $L'$ be the “padded” version of $L$ defined as the set of words of the form $x01^{|x|^2}$ for each $x ∈ L$. Now $L'$ is in SPACE($n$) because for an input of size $n$, no more than $\sqrt{n}$ characters are the original input and we can run the simulation of the original machine $M$ using space $n$.

A reduction from $L$ to $L'$ can be easily done in polynomial time, hence P=SPACE($n$)=SPACE($n^2$), and we get the desired contradiction with the Space Hierarchy Theorem.

Tomáš Janoušek
  • 209
  • That's not a problem. The whole argument is proof by contradiction; you've just provided a different contradiction. – Chad Groft Mar 13 '11 at 16:16
  • 3
    What I'm trying to say is that P=SPACE($n$) does not imply the existence of an algorithm to simulate any $n$-space Turing machine in $n^c$ time, hence the rest of the proof is irrelevant, not “just a difference contradiction”. – Tomáš Janoušek Mar 14 '11 at 00:04
  • @Tomáš: I first thought that @ScottAaronson may have assumed a universal (multitape) Turing machine that would be able to simulate any $n$-space machine with overhead that keeps the execution, say, in $2n$. But that also cannot be the full story, because the code of a particular LINSPACE machine can occupy more than $n^c$ tape fields and thus not meet the time limit without some further trick. – Jirka Hanika Mar 16 '12 at 21:52
3

In comparison to the existing answers, the following answer tries to better distinguish between complexity classes, languages in a complexity class, and words over the alphabet of a language.

Assume $\mathsf{P}=\mathsf{SPACE}(n)$. Then we can show that $L\in\mathsf{SPACE}(n^2)$ implies $L\in \mathsf{P}$. This is equivalent to $\mathsf{SPACE}(n^2)\subset \mathsf{P}=\mathsf{SPACE}(n)$, which contradicts the Space Hierarchy Theorem.

Let's show that $L\in\mathsf{SPACE}(n^2)$ would imply $L\in \mathsf{P}$, if $\mathsf{P}=\mathsf{SPACE}(n)$. Let $L \in \mathsf{SPACE}(n^2)$ be a language over the alphabet $\Sigma_L$, i.e. $L\subset \Sigma_L^*$. WLOG assume $\Sigma_L=\{0,1\}$. We define the "padding" function $f_L:\Sigma_L^*\to \Sigma_L^*$ via $f_L(w)=w01^{|w|^2-|w|}$, where $|w|$ is the length of the word $w$. Let $L':=f_L(L)$. We have $w\in L \Leftrightarrow f_L(w)\in L'$, because $f_L$ is injective. We have $L' \in \mathsf{SPACE}(n)$, because $|f_L(w)|=|w|^2+1$. (This point is already elaborated in the other answers.) We can now conclude $L\in \mathsf{P}$ based on our assumption $\mathsf{P}=\mathsf{SPACE}(n)$ and the fact that $f_L(w)$ can be computed in time $O(|w|^2)$.

Thomas Klimpel
  • 2,444
1

Assume by contradiction that P=SPACE(n). This means polynomial-time reduction is equivalent to linear space reduction. Therefore TQBF is PSPACE-complete in terms of both reductions. Since TQBF $\in$ SPACE(n), we conclude that PSPACE=SPACE(n)=P, contradicting the Space Hierarchy Theorem.

Y. Song
  • 11