How do I show that TQBF $\notin$ SPACE$((\log{n})^4)$? I know that TQBF is PSPACE complete, but is this the right approach?
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$– Luke MathiesonCommented 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$– user1526710Commented Apr 29, 2013 at 3:00
-
1$\begingroup$ Take a look at Corollary 5 on the Wikipedia page, does that get you closer? $\endgroup$– Luke MathiesonCommented Apr 29, 2013 at 3:30
-
$\begingroup$ How would I show that TQBF is one of these problems? $\endgroup$– user1526710Commented Apr 29, 2013 at 3:35
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Apr 29, 2013 at 3:37
$\begingroup$
$\endgroup$
8
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:
- If $|x| = n$, what can $|f(x)|$ be at most?
- Then how much space could you solve $x$ in if you could solve $f(x)$ with at most $O(\log^{4}n)$?
answered Apr 29, 2013 at 3:53
-
$\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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Apr 29, 2013 at 7:06