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

  • $\begingroup$ 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). $\endgroup$ – dkaeae Jun 14 at 7:13
  • $\begingroup$ Also, which is statement (iii)? $\endgroup$ – dkaeae Jun 14 at 7:13
  • $\begingroup$ Thank you for your response dkaeae. (iii) is $P \ne SPACE(n)$ $\endgroup$ – Stefano Ferraro Jun 14 at 7:28
  • $\begingroup$ OK, so (iii) is pretty much establishing a contradiction between (ii) and the hierarchy theorem. Can you take it from here? $\endgroup$ – dkaeae Jun 14 at 7:51
  • $\begingroup$ space heirachy thm already states $SPACE(n)\neq SPACE(n^2)$. Therefore $P\neq SPACE(n)$ simply by contrapositive argument. $\endgroup$ – Taylor Huang Jun 14 at 7:57

Your Answer

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

Browse other questions tagged or ask your own question.