2
$\begingroup$

According to Ryan Williams's answer $ALT\text{-}SPACE(a(n),\log n)\subseteq NSPACE(a(n)\log n)$.

Does there exist any better bound (for example something like $ALT\text{-}SPACE(a(n),\log n)\subseteq NSPACE(\log (a(n))\log n)$), or is it tight or an open problem?

$\endgroup$
2
$\begingroup$

It's open, at least for the inclusion $ALTSPACE(\alpha(n),\log n)\subseteq NSPACE(f(n))$ with $\Omega(\log n)\leq f(n)\leq \alpha(n)^{o(1)}$. According to Chandra, Kozen, and Stockmeyer, we know $$DTIME(n^k)\subseteq ALTSPACE(n^{2k},\log n)\subseteq \mathsf{P}.$$

Therefore if it is true, then $\mathsf{P}\neq \mathsf{NPSPACE}$ which is not known to be true. On the other hand, rejecting it will yield $\mathsf{P}\neq \mathsf{NL}$, which is also not known to hold.

$\endgroup$
  • $\begingroup$ Excuse me . I can't understand how $ALTSPACE(n^{2k},\log n)\subseteq P$. only things I know is $ASPACE(\log n)\subseteq P$ and the number of alternations is constant but if we replace the constant with a polynomial function how we could show that equation? can you explain a little more? Thank you again. $\endgroup$ – Mohsen Ghorbani Jul 24 '18 at 9:34
  • 2
    $\begingroup$ @MohsenGhorbani The proof of $ASPACE(\log n)\subseteq P$ works with any number of alternations, not only for constants. On the other hand with $s(n)=O(\log n)$ space there are at most $2^{O(s(n))}$ possible configurations, and thus $2^{O(s(n))}=n^{O(1)}$ alternations. $\endgroup$ – Willard Zhan Jul 24 '18 at 15:12

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.