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, 2013 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, 2013 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, 2013 at 5:29
  • $\begingroup$ This is actually not quite as easy as I had assumed. $\endgroup$ Dec 11, 2013 at 8:45
  • $\begingroup$ @Yuval, this is an exercise in Sipser about padding IIRC. $\endgroup$
    – Kaveh
    Feb 10, 2016 at 15:34

1 Answer 1

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, 2013 at 20:44
  • 1
    $\begingroup$ Different notions of reductions are used in different places. $\endgroup$ Dec 4, 2020 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, 2020 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, 2020 at 23:29
  • $\begingroup$ Ah, sorry...I see it now, it's bounded by Savitch's theorem. $\endgroup$
    – Macrophage
    Dec 4, 2020 at 23:33

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.