3
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ I cannot give you any more hints than the facts you've already mentioned. $\endgroup$ Nov 28 '13 at 2:12
  • 2
    $\begingroup$ 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.) $\endgroup$ Nov 28 '13 at 2:13
  • $\begingroup$ 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 $\endgroup$
    – InsigMath
    Nov 28 '13 at 5:29
  • $\begingroup$ This is actually not quite as easy as I had assumed. $\endgroup$ Dec 11 '13 at 8:45
  • $\begingroup$ @Yuval, this is an exercise in Sipser about padding IIRC. $\endgroup$
    – Kaveh
    Feb 10 '16 at 15:34
4
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ Hey @YuvalFilmus if you are interested in the solution to this problem, here is another version of this problem with exponent $n^{\frac{1}{4}}$ as solved by Professor Cook - cs.toronto.edu/~sacook/csc463h/problems/solutions4.pdf it's question 4 $\endgroup$
    – InsigMath
    Dec 16 '13 at 20:44
  • 1
    $\begingroup$ Different notions of reductions are used in different places. $\endgroup$ Dec 4 '20 at 22:21
  • $\begingroup$ Thanks, I just tried to derive that TQBF is indeed complete using logspace reduction. But I still have some question about what "blowing up" instances mean in your answer. I'm trying to prove by contradiction and somehow use the padding argument. $\endgroup$
    – Macrophage
    Dec 4 '20 at 23:27
  • $\begingroup$ More specifically, I'm wondering how we can put an upper bound on the size of the output of the logspace reduction to TQBF. $\endgroup$
    – Macrophage
    Dec 4 '20 at 23:29
  • $\begingroup$ Ah, sorry...I see it now, it's bounded by Savitch's theorem. $\endgroup$
    – Macrophage
    Dec 4 '20 at 23:33

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.