The Toda's theorem is a relationship between two different complexity classes: $ \# \mathsf{P} $ and $PH$. He proved that $ \mathsf{PH}\subseteq \mathsf{P}^{\#\mathsf{P}} $.

I wonder the following statement holds.

$ $ $\#\mathsf{P} \subseteq \mathsf{FP}^{\mathsf{PH}}$

If we prove this statement, $\# \mathsf{P}$ and $\mathsf{PH}$, that is, counting and alternation are $roughly$ $equivalent$ classes.


If your statement holds, then the polynomial hierarchy collapses: $\mathsf{\# P} \subseteq \mathsf{FP}^{\mathsf{PH}}$ iff $\mathsf{\# P} \subseteq \mathsf{FP}^{\mathsf{\Sigma_k P}}$ for some fixed $k$ (by definition). But then by Toda's Theorem we have $\mathsf{PH} \subseteq \mathsf{P}^{\mathsf{\# P}} \subseteq \mathsf{P}^{\mathsf{FP}^{\mathsf{\Sigma_k P}}} = \mathsf{P}^{\mathsf{\Sigma_k P}} = \mathsf{\Delta_{k+1} P}$.

  • $\begingroup$ Does $NP\subseteq P^{Mod_{k} P}$ and $coNP\subseteq P^{Mod_{k'} P}$ imply $PH\subseteq P^{Mod_{k''} P}$ at some $k''$? $\endgroup$ – 1.. Oct 31 '17 at 11:32
  • $\begingroup$ @777: $PH \subseteq P^{Mod_k P}$ unconditionally. $\endgroup$ – Joshua Grochow Nov 1 '17 at 2:40
  • $\begingroup$ I thought only PH in BPP^ModkP is known unconditionally. $\endgroup$ – 1.. Nov 1 '17 at 2:55
  • $\begingroup$ @777: Oh, sorry, you're right. The answer to your original question is yes, just take $k'' = k k'$ and use the fact that if $a | b$ then $Mod_a P \subseteq Mod_b P$. Then you get that both $NP,coNP$ are contained in $P^{Mod_{kk'} P}$, and you can do the usual thing to get the whole of $PH$ in there. I think you also need the fact that $Mod_a P$ is low for itself. $\endgroup$ – Joshua Grochow Nov 1 '17 at 5:51
  • $\begingroup$ sorry the steps are unclear to me. How does proof $NP\cup coNP\subset P^{Mod_aP}$ implies $PH\subset P^{Mod_aP}$ work? $\endgroup$ – 1.. Nov 8 '17 at 7:01

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.