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!



How do we know that P != LINSPACE without knowing if one is a subset of the other?
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.)


