4
$\begingroup$

Is there a version of Toda's theorem for intermediate levels of the polynomial hierarchy ? More precisely, is there any variant of the Toda's theorem that states:

Let $\# wSAT$ be the number of satisfying assignments to a boolean formula, where $(\log_2 n)^w$ variables (out of $n$) are assigned to TRUE.

$\bigcup_{i=1}^k \Sigma^P_k \subseteq P^{\# wSAT}$ ?

If something of this form is known, a reference would greatly help.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.