# Show that TQBF $\notin$ SPACE$((\log{n})^4)$?

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

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

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.

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)$?
• 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? Commented Apr 29, 2013 at 5:21
• Almost, you're definitely nearly there, your arithmetic is a bit wrong at the end though: $(\log(n^{d}))^{4} =\ldots$. Commented Apr 29, 2013 at 6:01
• you can solve $x$ in $(\log{n^d})^4 = d^4 \log^4{n} = O(\log^4{n})$? Commented Apr 29, 2013 at 6:44
• 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. Commented Apr 29, 2013 at 6:48
• 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? Commented Apr 29, 2013 at 7:06