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

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .