# Space(n) and Space(n^2) implications

I've a problem where I have to prove the following statements:

(i) if $$SPACE(n) \subseteq P \implies SPACE(n^2) \subseteq P$$

(ii) if $$P = SPACE(n) \implies SPACE(n) = SPACE(n^2)$$

For the Space Hierarchy Theorems we have that $$\forall f(n) = o(g(n)) \implies SPACE(g(n)) \nsubseteq SPACE(f(n))$$

Using this result and the statements (i) and (ii) I have to prove that (iii) $$P \neq SPACE(n)$$.

I'm using the following post as reference: https://mathoverflow.net/questions/40770/how-do-we-know-that-p-linspace-without-knowing-if-one-is-a-subset-of-the-othe/333956#333956

I suppose that I can use Thomas Klimpel's proof in the abovementioned link to prove the statement (i). But how can I prove the statements (ii) and (iii)?

Accept my apologies for this question, but I'm a rookie in Theory of Complexity :)

• Once you've established (i), (ii) is pretty basic. Just consider the two inclusions you need to prove (one is trivial, and the other is simply the premise of the implication). – dkaeae Jun 14 at 7:13
• Also, which is statement (iii)? – dkaeae Jun 14 at 7:13
• Thank you for your response dkaeae. (iii) is $P \ne SPACE(n)$ – Stefano Ferraro Jun 14 at 7:28
• OK, so (iii) is pretty much establishing a contradiction between (ii) and the hierarchy theorem. Can you take it from here? – dkaeae Jun 14 at 7:51
• space heirachy thm already states $SPACE(n)\neq SPACE(n^2)$. Therefore $P\neq SPACE(n)$ simply by contrapositive argument. – Taylor Huang Jun 14 at 7:57