# Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?

If $A$ is a PSPACE-complete language, $P^{A}=NP^{A}$.

If $B$ is a deterministic polynomial-time oracle, $P^{B}\ne NP^{B}$ (assuming $P\ne NP$).

$PP$ is the class of decision problems analog for $\#P$ and $P\subseteq PP\subseteq PSPACE$,

but neither $P=PP$ nor $PP=PSAPCE$ is known. But is it true that

$coNP^{\#P}=NP^{\#P}=P^{\#P}$?

• If $B$ is a deterministic polynomial time oracle, I guess you mean we believe $P^B \neq NP^B$. (since $P^B = P$ and $NP^B = NP$) Commented Oct 30, 2010 at 8:14
• I might be wrong, but let me give it a try: Your 1st question assumes the second containment is not strict. In other words, it assumes that PP=PSPACE. In that case, I think the equality holds by the result you mentioned at the beginning. Am I right? (P.S: The reverse holds for the 2nd question.) Commented Oct 30, 2010 at 10:10
• Toda's Theorem might be relevant here, as it indicates one might be able to fold the difference between $P$ and $NP$ to the $#P$ oracle. (But I'm not 100% sure about it.) Commented Nov 1, 2010 at 2:40
• The answer to your fourth question is yes. Even NP^PSPACE is contained in PSPACE, so surely NP with a #P oracle is in PSPACE. Commented Nov 1, 2010 at 3:28
• As the comments suggest, some of the questions stated in this post (and some of the questions you recently added) are basic. Please show some evidence that you really care. See also meta.cstheory.stackexchange.com/questions/300/…, meta.cstheory.stackexchange.com/questions/300/…. Commented Nov 18, 2010 at 1:40

It is an open problem in complexity theory for many years if $\mathsf{PH}^{\mathsf{\#P}}$ collapse, where $\mathsf{PH}$ is the polynomial time hierarchy. It is also an open problem to construct an oracle to separate $\mathsf{P}^{\mathsf{\#P}}$ from $\mathsf{PSPACE}$.

• Welcome to CSTheory.SE, @Bin Fu! :) Commented Feb 1, 2011 at 17:20
• Or maybe you were here before, but welcome anyway! ;) Commented Feb 1, 2011 at 17:28
• Thanks, Daniel Apon. It is known that PH^{Parity P} collapses. It will be very interesting if one can prove PH^{#P} collapses. Commented Feb 2, 2011 at 16:27
• Interesting, could you provide a reference for $PH^{\#P}$ and the problem of its collapse, please? Commented Jun 2, 2015 at 9:03

If I do not interpret it wrongly. Theorem 4.1(ii) is saying "$NP^{\mathbf{C}K}=\exists \mathbf{C}K$" and $coNP^{\mathbf{C}K}=\forall\mathbf{C}K$.

Lemma 3.4(c) is saying "For any $K$ in counting hierarchy, $\exists K\cup\forall K\subseteq\mathbf{C}K\subseteq\exists\mathbf{C}K\cap\forall\mathbf{C}K$".

Replacing $K$ by $P$, we get $PP\subseteq\exists PP\cap\forall PP$.

Which means $P^{\#P}\subseteq NP^{\#P}\cap coNP^{\#P}$.

And $P^{\#P}=NP^{\#P}=coNP^{\#P}$ holds if the polynomial hierarchy collapses and the counting hierarchy collapses.

• The inclusion P^X ⊆ NP^X ∩ coNP^X for any class X is clear from the definition, and you do not need Theorem 4.1 of Torán for this. I cannot see why the collapses of the polynomial hierarchy and the counting hierarchy imply P^#P = NP^#P = coNP^#P. Can you elaborate? Commented Nov 19, 2010 at 22:51
• @Tsuyoshi: If the polynomial hierarchy collapses, $P=NP=coNP$, then $P^{\#P}=NP^{\#P}=coNP^{\#P}$. If the counting hierarchy collapses, then $\mathbf{C}\mathbf{C}P=\mathbf{C}P$, i.e. $PP^{PP}=PP$. By lemma 3.4(c), $\exists K\cup\forall K\subseteq\mathbf{C}K$, so $P^{\#P}\subseteq NP^{\#P}\cap coNP^{\#P}$$\subseteq NP^{\#P}\cup coNP^{\#P}\subseteq PP^{PP}$$=PP=P^{\#P}$, which means $\subseteq$ in this formula should be $=$ instead. Commented Nov 19, 2010 at 23:35
• “The polynomial hierarchy collapses” does not necessarily mean P=NP, and “the counting hierarchy collapses” does not necessarily mean PP=PP^PP. Commented Nov 20, 2010 at 2:01
• In addition, P=NP does not imply P^#P=NP^#P as far as I know (but I may be missing something). Commented Nov 20, 2010 at 3:09
• A common mistake in these type of arguments is to assume relativizing to an oracle is an operation on the collection of languages, but it is instead an operation ont the type of computation, which drastically affects what languages are in the class. Commented Feb 1, 2011 at 17:48