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

CC BY-SA 3.0
2017-10-31T11:32:33.020Z
Does $NP\subseteq P^{Mod_{k} P}$ and $coNP\subseteq P^{Mod_{k'} P}$ imply $PH\subseteq P^{Mod_{k''} P}$ at some $k''$?
Turbo
CC BY-SA 3.0
2017-11-01T02:40:55.070Z
@777: $PH \subseteq P^{Mod_k P}$ unconditionally.
Joshua Grochow
CC BY-SA 3.0
2017-11-01T02:55:40.510Z
I thought only PH in BPP^ModkP is known unconditionally.
Turbo
CC BY-SA 3.0
2017-11-01T05:51:50.497Z
@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.
Joshua Grochow
CC BY-SA 3.0
2017-11-08T07:01:07.493Z
sorry the steps are unclear to me. How does proof $NP\cup coNP\subset P^{Mod_aP}$ implies $PH\subset P^{Mod_aP}$ work?
Turbo
CC BY-SA 3.0
2017-11-08T16:37:13.250Z
@777: A good fraction of my time on this site is spent answering *your* questions, including questions like this that you ask in the comments, which are not really what the comments are for. Nonetheless, this suggests an overlap of interests. If you want an answer to this one, please email me. It would be nice to know who you are and, much more importantly, have a real conversation that doesn't fit into this public and character-limited format. Sincerely, Josh.
Joshua Grochow
CC BY-SA 3.0
2014-07-25T15:30:13.820Z
2014-07-25T15:30:13.820Z
Joshua Grochow
<p>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}} $.</p>

<p>I wonder the following statement holds.</p>

<blockquote>
  <p>$ $    $\#\mathsf{P} \subseteq \mathsf{FP}^{\mathsf{PH}}$ </p>
</blockquote>

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

<cc.complexity-theory><complexity-classes><counting-complexity>
Does $\# \mathsf{P}\subseteq \mathsf{FP}^{\mathsf{PH}}$?
shen
# Does $\# \mathsf{P}\subseteq \mathsf{FP}^{\mathsf{PH}}$?

(Asked by: username_0 on 2014-07-25)

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.

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity

---

## 1 answers

### Answer by username_1 on 2014-07-25. Score: 9

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

> **Comments:**
> **username_2**: Does $NP\subseteq P^{Mod_{k} P}$ and $coNP\subseteq P^{Mod_{k'} P}$ imply $PH\subseteq P^{Mod_{k''} P}$ at some $k''$?  
> **username_1**: @777: $PH \subseteq P^{Mod_k P}$ unconditionally.  
> **username_2**: I thought only PH in BPP^ModkP is known unconditionally.  
> **username_1**: @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.  
> **username_2**: sorry the steps are unclear to me. How does proof $NP\cup coNP\subset P^{Mod_aP}$ implies $PH\subset P^{Mod_aP}$ work?  
> **username_1**: @777: A good fraction of my time on this site is spent answering *your* questions, including questions like this that you ask in the comments, which are not really what the comments are for. Nonetheless, this suggests an overlap of interests. If you want an answer to this one, please email me. It would be nice to know who you are and, much more importantly, have a real conversation that doesn't fit into this public and character-limited format. Sincerely, Josh.  

---

