0
$\begingroup$

Condidering the proof, NLOGSPACE$\subset$PSPACE

I wrote following proof:

NLOGSPACE = NSPACE$(\log n)$ $\hspace{15pt} \because$ Definition of NLOGSPACE

NSPACE$(\log n)$ $\subseteq$ DSPACE$(\log^2 n)$ $\hspace{15pt} \because$ Theorem(1)

We let $m = \log n$, then,

DSPACE$(m^2)$ $\subset$PSPACE $\hspace{15pt} \because$ Definition(2)

Therefore, NLOGSPACE$\subset$PSPACE.

Theorem(1): If $S$ is a space constructible function and $S(n) \ge \log n$, then NSPACE$(S(n)) \subseteq$ DSPACE$(S^2(n))$.

definition(2): PSPACE = DSPACE$(n)$$\cup$DSPACE$(n^2)$$\cup$DSPACE$(n^3)$$\cup$...$\cup$DSPACE$(n^k)$$\cup$...

But I am still not that sure if that "We let $m = \log n$" is ok, is this proving NLOGSPACE$\subset$PSPACE?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

What would you think about a proof that says the following?

  • $NP \subset DTIME(2^n)$
  • let $m = \log n$, then $DTIME(2^n) = DTIME(m) \subset P$
  • Therefore $P = NP$

Here, you have indeed $DPSACE(log^2n)\subset PSPACE$ but the argument is weird.

Also please note that Savitch's theorem already proves that $NPSPACE \subset PSPACE$, and you have the result you want, since $NLOGSPACE \subset NPSPACE$.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thanks for answering! How Savitch's theorem proves NPSPACE⊂PSPACE? also, where is NLOGSPACE⊂NPSPACE? $\endgroup$
    – t24akeru
    Apr 24, 2021 at 9:31
  • $\begingroup$ The first question is true because if $f$ is a polynomial function, then $f^2$ is a polynomial function too. And $NPSPACE = \underset{f\text{ polynomial}}{NSPACE}(f(n)) \subset \underset{f\text{ polynomial}}{DSPAC}E(f(n)^2) = PSPACE$. $\endgroup$
    – Nathaniel
    Apr 24, 2021 at 9:40
  • $\begingroup$ The second question is true because $\log n = O(n)$, and so $NLOGSPACE = NSPACE(\log n) \subset DSPACE((\log n)^2) \subset DSPACE(n^2) \subset PSPACE$ $\endgroup$
    – Nathaniel
    Apr 24, 2021 at 9:43
  • $\begingroup$ I see. At $DSPACE(f(n)^2) = PSPACE$, why can you write "=", not "$\subset$"? $\endgroup$
    – t24akeru
    Apr 24, 2021 at 10:06
  • $\begingroup$ Because the union is done on all polynomial functions. $\endgroup$
    – Nathaniel
    Apr 24, 2021 at 10:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.