# Prove that $TQBF \notin SPACE(n^{\frac{1}{3}})$

I would like some hints on how to approach this problem, I know for instance that $TQBF$ is $PSPACE$-$Complete$, so it can solved in poly space and any other $PSPACE$-$Complete$ problems can be log spaced reduced to $TQBF$. I believe that I need to employ the space hierarchy theorem in some way but I am not sure how, this is a homework question so I just want a hints. Thank you!

• I cannot give you any more hints than the facts you've already mentioned. – Yuval Filmus Nov 28 '13 at 2:12
• By the way, TQBF being PSPACE-complete means that TQBF is in PSPACE, and any problem in PSPACE is polytime-reducible to it. (Perhaps even logspace-reducible.) – Yuval Filmus Nov 28 '13 at 2:13
• Thanks we were told that it is logspace reducible. I understand that you cannot give anymore hints without basically spelling out the solution. I will think more deeply about this question. Have a good evening @YuvalFilmus – InsigMath Nov 28 '13 at 5:29
• This is actually not quite as easy as I had assumed. – Yuval Filmus Dec 11 '13 at 8:45
• @Yuval, this is an exercise in Sipser about padding IIRC. – Kaveh Feb 10 '16 at 15:34

The argument is actually surprisingly delicate. This sketch follows Tompa's Introduction to computational complexity, Chapter 10. The space hierarchy theorem shows that there is some problem $L \in \mathrm{SPACE}(n^{1+\epsilon}) \setminus \mathrm{SPACE}(n)$ for every $\epsilon > 0$. Since TQBF is PSPACE-complete, there is some logspace reduction from $L$ to TQBF. But we actually know more - using Savitch's theorem, we can come up with some reduction which blows up instances of $L$ of size $n$ to instances of TQBF of size $O(n^{2(1+\epsilon)} \log n)$ (at least according to Ryan Williams, page 1 at the bottom). If TQBF were solvable in space $O(n^\delta)$ then this would give an algorithm for $L$ in space $O(n^{2\delta(1+\epsilon)})$. Taking the limit $\epsilon \to 0$, this shows that $\delta \geq 1/2$.