A remarkable feature of the reduction showing that TQBF (True Quantified Boolean Formulas) is PSPACE-complete is that it actually runs in logspace, i.e. for any $A \in \mathsf{PSPACE}$, $$ A \le_L TQBF. $$ (See for example, comment at the end of section 7.4 in these notes.) Therefore, TQBF is complete with respect to logspace reductions. It is still possible, however, that there are some other standard PSPACE-complete problems for which this is not true. Of course, the problem would reduce in logspace to TQBF, but maybe the reduction the other way would not go through.

Question: If $A$ is PSPACE-complete, must $A$ be complete with respect to logspace reductions? In other words, if $A \in \textsf{PSPACE}$ and $TQBF \le_p A$, then must $TQBF \le_L A$?

Some thoughts:

I tried the generalized geography problem, and it seems to be true in that case. I'm not sure about universality for NFAs.

To prove it, the most straightforward idea would be to show that if $A \le_p B$ and $B \le_L A$, then $A \le_L B$. But this is false for general $A, B$, assuming $\mathsf{L} \ne \mathsf{P}$. In particular, take $A \in \mathsf{P}$ and $B = \varnothing$.

  • 1
    $\begingroup$ As a general rule of thumb, the answer to the question "If we make this small change to the definition of some concept in complexity theory, does it make any difference?" is "We don't know." For example, we don't know if defining NP-completeness in terms of polytime, logspace or first-order reductions leads to the same set of problems being called NP-complete. $\endgroup$ – David Richerby Apr 11 '18 at 21:39

If every PSPACE complete problem is also complete under logspace reduction, then $\mathsf{P\neq PSPACE}$.

To see why, suppose for the purpose of contradiction that the definition of completeness remains unchanged when replacing polynomial time with logspace reductions, and simultaneously $\mathsf{P=PSPACE}$. Since $\mathsf{P=PSPACE}$, every nontrivial language in PSPACE is complete under polynomial time reductions, e.g. undirected connectivity which lies is $\mathsf{L}$. Seeing that we assumed that polynomial time completeneess is equivalent to logspace completeness, undirected conectivity is also PSPACE complete under logspace reductions, which implies $\mathsf{L=PSPACE}$, contradicting the space hierarchy theorem.

This question is probably still open (though I am unaware of any important/strange implications of the negation of your statement). You can find similar discussions about NP-completeness, where it appears the same question is also open.

| cite | improve this answer | |
  • $\begingroup$ Thanks, that's very nice, a more complete answer than I was expecting. $\endgroup$ – 6005 Apr 11 '18 at 22:22

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.