2
$\begingroup$

How do I show that TQBF $\notin$ SPACE$((\log{n})^4)$? I know that TQBF is PSPACE complete, but is this the right approach?

$\endgroup$
4
  • 2
    $\begingroup$ Have you had a look at the Space Hierarchy Theorem? (Assuming that you're not for some reason restricted from using it. $\endgroup$ Apr 29, 2013 at 2:57
  • $\begingroup$ I know the Space Hierarchy Theorem. I don't "see" how it applies to the problem though. $\endgroup$ Apr 29, 2013 at 3:00
  • 1
    $\begingroup$ Take a look at Corollary 5 on the Wikipedia page, does that get you closer? $\endgroup$ Apr 29, 2013 at 3:30
  • $\begingroup$ How would I show that TQBF is one of these problems? $\endgroup$ Apr 29, 2013 at 3:35

2 Answers 2

5
$\begingroup$

Hint: TQBF is PSPACE-complete, so it "requires" polynomial space. If there were an algorithm to solve TQBF using space $O(\log^4 n)$, you could use it to solve all problems in PSPACE using surprisingly small space. So surprising, in fact, that the space hierarchy theorem says it can't be.

$\endgroup$
2
$\begingroup$

Another hint: As $TQBF$ is PSPACE-complete, for every problem $L$ in PSPACE, there exists a reduction $f$ such that for every instance $x$ of $L$ we can construct an instance $f(x)$ of $TQBF$ in time $O(n^{d})$ for some $d\in\mathbb{N}$ (note that $d$ depends on $f$, so it's unbounded, it can be different for every $f$).

Then there's two questions:

  1. If $|x| = n$, what can $|f(x)|$ be at most?
  2. Then how much space could you solve $x$ in if you could solve $f(x)$ with at most $O(\log^{4}n)$?
$\endgroup$
8
  • $\begingroup$ For part 1, so if $|x|=n$, then $|f(x)|$ is at most $O(n^d)$, since $f$ runs for $O(n^d)$ steps, and adds something for each step. For part 2, you can solve $x$ in $O(n^{1/d}\log^4{n})$ space, right? $\endgroup$ Apr 29, 2013 at 5:21
  • $\begingroup$ Almost, you're definitely nearly there, your arithmetic is a bit wrong at the end though: $(\log(n^{d}))^{4} =\ldots$. $\endgroup$ Apr 29, 2013 at 6:01
  • $\begingroup$ you can solve $x$ in $(\log{n^d})^4 = d^4 \log^4{n} = O(\log^4{n})$? $\endgroup$ Apr 29, 2013 at 6:44
  • 1
    $\begingroup$ Thereabouts, if you want to overkill it, $\ldots = d^{4}\log^{4}n \leq n^{8} \in O(n^{8})$, and we've contradicted the Space Hierarchy Theorem. $\endgroup$ Apr 29, 2013 at 6:48
  • $\begingroup$ Aha! So you can conclude that $(\forall L \in PSPACE) L$ is decidable in $O(n^d)$ space and in $O(\log^4{n}) = o(n^d)$ space, and so no language exists that is decidable in $O(n^d)$ and not in $o(n^d)$, right? $\endgroup$ Apr 29, 2013 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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