<p>By <a href="http://portal.acm.org/citation.cfm?id=116858" rel="nofollow">http://portal.acm.org/citation.cfm?id=116858</a></p>

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

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

<p>Replacing $K$ by $P$, we get $PP\subseteq\exists PP\cap\forall PP$.</p>

<p>Which means $P^{\#P}\subseteq NP^{\#P}\cap coNP^{\#P}$.</p>

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

CC BY-SA 2.5
2010-11-19T22:51:50.657Z
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?
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-19T23:35:52.147Z
@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.
Mike Chen
CC BY-SA 2.5
2010-11-20T02:01:14.983Z
“The polynomial hierarchy collapses” does not necessarily mean P=NP, and “the counting hierarchy collapses” does not necessarily mean PP=PP^PP.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-20T03:09:26.510Z
In addition, P=NP does not imply P^#P=NP^#P as far as I know (but I may be missing something).
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-01T17:48:00.910Z
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.
Derrick Stolee
CC BY-SA 3.0
2013-03-27T20:17:33.223Z
I would replace #P with PP and then you can definitely see that P^PP does not equal P^NP. Even if P=NP then you do not know if that equality will absorb PP into P as well.
Tayfun Pay
CC BY-SA 2.5
2010-11-19T20:56:01.373Z
2010-11-19T20:56:01.373Z
Mike Chen
<p>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}$.</p>

CC BY-SA 3.0
2015-06-02T09:03:53.940Z
Interesting, could you provide a reference for $PH^{\#P}$ and the problem of its collapse, please?
neophyte
CC BY-SA 2.5
2011-02-01T17:20:56.057Z
Welcome to CSTheory.SE, @Bin Fu! :)
Daniel Apon
CC BY-SA 2.5
2011-02-01T17:28:34.077Z
Or maybe you were here before, but welcome anyway! ;)
Daniel Apon
CC BY-SA 2.5
2011-02-02T16:27:46.363Z
Thanks, Daniel Apon. It is known that PH^{Parity P} collapses. It will be very interesting if one can prove PH^{#P} collapses.
Bin Fu
CC BY-SA 2.5
2011-02-01T16:56:30.980Z
2011-02-02T04:46:09.153Z
2011-02-02T04:46:09.153Z
Bin Fu
<p>By <a href="http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf" rel="nofollow">http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf</a></p>

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

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

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

<p>but neither $P=PP$ nor $PP=PSAPCE$ is known. But is it true that</p>

<p>$coNP^{\#P}=NP^{\#P}=P^{\#P}$?</p>

CC BY-SA 2.5
2010-10-30T08:14:21.373Z
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$)
Ramprasad
CC BY-SA 2.5
2010-10-30T08:25:19.530Z
@Ramprasad: Exactly
Mike Chen
CC BY-SA 2.5
2010-10-30T10:10:08.873Z
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.)
Sadeq Dousti
CC BY-SA 2.5
2010-11-01T01:17:21.500Z
@Sadeq: I think you are right. But the problem is we don't know which containment is strict. 3 & 4 may be more challenging.
Mike Chen
CC BY-SA 2.5
2010-11-01T02:40:18.840Z
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.)
Boaz Barak
CC BY-SA 2.5
2010-11-01T03:28:40.040Z
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.
Robin Kothari
CC BY-SA 2.5
2010-11-18T01:22:07.247Z
I read revision 7.  What do you mean by FP?  If it refers to the class of polynomial-time computable functions, you cannot compare NP^#P to FP^#P because NP^#P is a class of _decision problems_ and FP^#P is a class of _functions_ (type error!).
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-18T01:33:51.320Z
@Tsuyoshi: My mistake, fixed now.
Mike Chen
CC BY-SA 2.5
2010-11-18T01:40:53.757Z
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 http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/304#304, http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/306#306.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-18T01:49:38.107Z
By the way, I have to point out that most part of the quesiton looks like homework to me, although if it is, it is stated in a deliberately confusing way.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-18T04:24:56.520Z
@Tsuyoshi: Thank you for your comments. To be honest, I am beginner in Computational complexity. Sometimes, I feel confused when reading complexity books. Toda's theorem points out $PH\subseteq P^{\#P}=P^{PP}$, but it doesn't say anything about $NP^{\#P}$ and $coNP^{\#P}$, which to my mind seem to be equal. Plus, I almost can't find any literatures about $NP^{\#P}$ and $coNP^{\#P}$. Anyways, sorry for the confusions and thank you again for your comments.
Mike Chen
CC BY-SA 2.5
2010-11-18T12:40:51.517Z
I read revision 9.  (1) I think that the question is becoming interesting.  Thank you for revising the question.  And I hope that other people who answered the deleted part of the question are also fine with it (my guess is that that is why people posted their answers as comments, although I am not completely sure).  (2) Can you clarify what you mean by “PP is neither a PSPACE-complete language nor a deterministic polynomial time language”?  Needless to say, whether PP=PSPACE and whether P=PP are currently both unknown.  (Moreover, PP is a class, not a language!)
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-18T13:08:11.410Z
@Tsuyoshi: I second that ;) I would correct the sentence you mentioned as: “assuming PP neither equals PSPACE nor P, is it true that...”
Sadeq Dousti
<cc.complexity-theory><complexity-classes><counting-complexity><open-problem><oracles>
Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?
Mike Chen
# Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?

(Asked by: username_0 on 2010-10-30)

By <http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf>

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

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, open-problem, oracles
> **Comments:**
> **username_1**: 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$)  
> **username_0**: @Ramprasad: Exactly  
> **username_2**: 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.)  
> **username_0**: @Sadeq: I think you are right. But the problem is we don't know which containment is strict. 3 & 4 may be more challenging.  
> **username_3**: 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.)  
> **username_4**: 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.  
> **username_5**: I read revision 7.  What do you mean by FP?  If it refers to the class of polynomial-time computable functions, you cannot compare NP^#P to FP^#P because NP^#P is a class of _decision problems_ and FP^#P is a class of _functions_ (type error!).  
> **username_0**: @Tsuyoshi: My mistake, fixed now.  
> **username_5**: 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 http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/304#304, http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/306#306.  
> **username_5**: By the way, I have to point out that most part of the quesiton looks like homework to me, although if it is, it is stated in a deliberately confusing way.  
> **username_0**: @Tsuyoshi: Thank you for your comments. To be honest, I am beginner in Computational complexity. Sometimes, I feel confused when reading complexity books. Toda's theorem points out $PH\subseteq P^{\#P}=P^{PP}$, but it doesn't say anything about $NP^{\#P}$ and $coNP^{\#P}$, which to my mind seem to be equal. Plus, I almost can't find any literatures about $NP^{\#P}$ and $coNP^{\#P}$. Anyways, sorry for the confusions and thank you again for your comments.  
> **username_5**: I read revision 9.  (1) I think that the question is becoming interesting.  Thank you for revising the question.  And I hope that other people who answered the deleted part of the question are also fine with it (my guess is that that is why people posted their answers as comments, although I am not completely sure).  (2) Can you clarify what you mean by “PP is neither a PSPACE-complete language nor a deterministic polynomial time language”?  Needless to say, whether PP=PSPACE and whether P=PP are currently both unknown.  (Moreover, PP is a class, not a language!)  
> **username_2**: @Tsuyoshi: I second that ;) I would correct the sentence you mentioned as: “assuming PP neither equals PSPACE nor P, is it true that...”  

---

## 2 answers

### Answer by username_8 on 2011-02-01. Score: 12 | Accepted answer

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

> **Comments:**
> **username_10**: Welcome to CSTheory.SE, @Bin Fu! :)  
> **username_10**: Or maybe you were here before, but welcome anyway! ;)  
> **username_8**: Thanks, Daniel Apon. It is known that PH^{Parity P} collapses. It will be very interesting if one can prove PH^{#P} collapses.  
> **username_9**: Interesting, could you provide a reference for $PH^{\#P}$ and the problem of its collapse, please?  

---

### Answer by username_0 on 2010-11-19. Score: 0

By <http://portal.acm.org/citation.cfm?id=116858>

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.

> **Comments:**
> **username_5**: 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?  
> **username_0**: @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.  
> **username_5**: “The polynomial hierarchy collapses” does not necessarily mean P=NP, and “the counting hierarchy collapses” does not necessarily mean PP=PP^PP.  
> **username_5**: In addition, P=NP does not imply P^#P=NP^#P as far as I know (but I may be missing something).  
> **username_6**: 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.  
> **username_7**: I would replace #P with PP and then you can definitely see that P^PP does not equal P^NP. Even if P=NP then you do not know if that equality will absorb PP into P as well.  

---

