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!

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