1
$\begingroup$

It is known that $QSAT$ is $PSPACE$ complete, and it is known that $QSAT_i$ is $\Sigma_i$ complete for any constant $i$. However, what if we had $QSAT_{\log n}$? That is, $QSAT$ where the quantifiers can alternate $\omega(1)$ times, but still $o(n)$. Would this be enough to make the problem $PSPACE$ complete, or are all $O(n)$ alternations necessary? If this is not $PSPACE$ hard, would it fit somewhere in $PH$?

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $\Sigma_{O(\log n)} \mathrm{P}$ be the class of languages accepted by a polynomial-time alternative Turing machine with $O(\log n)$ alternations. Then, $QSAT_{\log n}$ is complete for this complexity class (under polynomial-time many-one reduction, for example). This question in TCS.SE Quantified Boolean Formulas with logarithmic alternations has some more discussions of this complexity class.

If this is not PSPACE hard, would it fit somewhere in PH?

The problem is $PH$-hard because $QSAT_i$ is $\Sigma_{i+1}$-complete for every $i$ and we have $i \in O(\log n)$ for all constant $i$.

$\endgroup$

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.