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

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.

## 1 Answer

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}$.

• Does $NP\subseteq P^{Mod_{k} P}$ and $coNP\subseteq P^{Mod_{k'} P}$ imply $PH\subseteq P^{Mod_{k''} P}$ at some $k''$?
– Mr.
Oct 31 '17 at 11:32
• @777: $PH \subseteq P^{Mod_k P}$ unconditionally. Nov 1 '17 at 2:40
• I thought only PH in BPP^ModkP is known unconditionally.
– Mr.
Nov 1 '17 at 2:55
• @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. Nov 1 '17 at 5:51
• sorry the steps are unclear to me. How does proof $NP\cup coNP\subset P^{Mod_aP}$ implies $PH\subset P^{Mod_aP}$ work?
– Mr.
Nov 8 '17 at 7:01