<p>This is an open question. If it is to be true the consequences would imply the collapse of the ${\bf Counting-Hierarchy}$, ${\bf CH}$ for short. In the paper "On the closure properties of #P in the context of PF o #" by Ogihara, Toda, Watanabe and Thierauf" on proposition 2.1 it is stated that </p>

<p>${\bf NP ^{PP}} \subseteq {\bf P^{\#P^{[1]}}} $ if and only if ${\bf CH} = {\bf P^{\#P^{[1]}}} $ if and only if ${\bf FP ^{CH}} \subseteq {\bf FP^{\#P^{[1]}}} $.</p>

CC BY-SA 3.0
2013-12-08T21:33:57.383Z
You also need that P^#P = P^#P[1] (proven in Toda's paper Simple characterizations of P(#P) and complete problems) to get the conclusion that NP^PP = P^PP implies that CH collapses.
Lance Fortnow
CC BY-SA 3.0
2013-12-08T23:56:58.617Z
@Tayfun: I cannot apply your argumentation for the collapse of the CH to my initial question, since as Lance pointed out, we additionally need P^#P = P^#P[1].
Dennis Weyland
CC BY-SA 3.0
2013-12-08T23:57:25.103Z
@Lance: I am reading your answer as P^#P = P^#P[1]. This confuses me even more, although it would fix the argumentation of Tayfun.
Dennis Weyland
CC BY-SA 3.0
2013-12-10T03:03:51.993Z
It would be awesome, if you could provide me just a tiny bit more of information: 1) Which of Toda's papers? 2) Which result in that paper? 3) With "my answer" you refer to proposition 2.1 in the paper of Ogihara, Toda, Watanabe, Thierauf? thanks a lot...
Dennis Weyland
CC BY-SA 3.0
2013-12-21T22:09:47.357Z
@DennisWeyland What Lance is referring to is in Toda's Paper "Simple Characterizations of P(#P) and complete problems" Theorem 3.2., which states that ${\bf FP ^{\#P^{NP}}} \subseteq {\bf FP^{FP^{\#P_{[1]}}}} \subseteq {\bf FP ^{\#P}}$.
Tayfun Pay
CC BY-SA 3.0
2013-12-07T02:31:05.220Z
2013-12-07T02:31:05.220Z
Tayfun Pay
<p>I thought the relation between P using a #P-oracle and NP using a #P-oracle is still unknown (or equivalently the relation between P^PP and NP^PP).</p>

<p>Recently, I have read in a journal article that P^#P = NP^#P (citing Toda's publication "PP is as hard as the polynomial time hierarchy"). As far as I remember this relation was posed as an open question in Toda's paper.</p>

<p>I am very confused at the moment and I would be glad if someone could clarify this situation. Thanks a lot.</p>

CC BY-SA 3.0
2013-12-06T23:41:56.767Z
Check out the paper "Satanic notations: Counting Classes beyond #P and Other Definitional Adventures" by Hemaspaandra and Vollmer
Tayfun Pay
CC BY-SA 3.0
2013-12-07T00:44:09.543Z
I just had a quick look at this paper. Unfortunately, I do not see the connection to my question. In fact, I even do not see where they use #P as an oracle in any of their results. Could you be so kind and give me a hint about the actual part of the paper you had in mind?
Dennis Weyland
CC BY-SA 3.0
2013-12-07T01:01:04.487Z
Very good. In my opinion that is like a reference point to the papers on #P as well as some other complexity classes. It connects a lot of dots in a good way. Anyways, you should have made your way to the following paper from that paper "Polynomial time 1-Turing Reductions from #PH to #P". by Toda and Watanabe. Ok
Tayfun Pay
CC BY-SA 3.0
2013-12-07T01:23:52.273Z
I don't want to be unpolite, but I did not ask for references about papers handling counting problems. My question is the following: Has the long standing open problem about the relation between P^#P and NP^#P (are they equal or not) been settled? I was sure it is still open, but I have read in a paper from 2005 that "... is in the class NP^#P = P^#P" and now I am confused.
Dennis Weyland
CC BY-SA 3.0
2013-12-07T01:52:47.170Z
Why don't you cite that paper?
Tayfun Pay
CC BY-SA 3.0
2013-12-07T02:02:33.480Z
because i don't want to make the authors appear in a negative light. and the only important thing is that they state "... is in the class NP^#P = P^#P". that means they state that relative to a #P-oracle, P is equal to NP. and as far as i know the relation between NP^#P and P^#P is still an open problem. I am quite sure, but I would like to get some sort of confirmation...
Dennis Weyland
<cc.complexity-theory><counting-complexity>
Do we know whether P^#P = NP^#P?
Dennis Weyland
# Do we know whether P^#P = NP^#P?

(Asked by: username_0 on 2013-12-06)

I thought the relation between P using a #P-oracle and NP using a #P-oracle is still unknown (or equivalently the relation between P^PP and NP^PP).

Recently, I have read in a journal article that P^#P = NP^#P (citing Toda's publication "PP is as hard as the polynomial time hierarchy"). As far as I remember this relation was posed as an open question in Toda's paper.

I am very confused at the moment and I would be glad if someone could clarify this situation. Thanks a lot.

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

> **Comments:**
> **username_1**: Check out the paper "Satanic notations: Counting Classes beyond #P and Other Definitional Adventures" by Hemaspaandra and Vollmer  
> **username_0**: I just had a quick look at this paper. Unfortunately, I do not see the connection to my question. In fact, I even do not see where they use #P as an oracle in any of their results. Could you be so kind and give me a hint about the actual part of the paper you had in mind?  
> **username_1**: Very good. In my opinion that is like a reference point to the papers on #P as well as some other complexity classes. It connects a lot of dots in a good way. Anyways, you should have made your way to the following paper from that paper "Polynomial time 1-Turing Reductions from #PH to #P". by Toda and Watanabe. Ok  
> **username_0**: I don't want to be unpolite, but I did not ask for references about papers handling counting problems. My question is the following: Has the long standing open problem about the relation between P^#P and NP^#P (are they equal or not) been settled? I was sure it is still open, but I have read in a paper from 2005 that "... is in the class NP^#P = P^#P" and now I am confused.  
> **username_1**: Why don't you cite that paper?  
> **username_0**: because i don't want to make the authors appear in a negative light. and the only important thing is that they state "... is in the class NP^#P = P^#P". that means they state that relative to a #P-oracle, P is equal to NP. and as far as i know the relation between NP^#P and P^#P is still an open problem. I am quite sure, but I would like to get some sort of confirmation...  

---

## 1 answers

### Answer by username_1 on 2013-12-07. Score: 6

This is an open question. If it is to be true the consequences would imply the collapse of the ${\bf Counting-Hierarchy}$, ${\bf CH}$ for short. In the paper "On the closure properties of #P in the context of PF o #" by Ogihara, Toda, Watanabe and Thierauf" on proposition 2.1 it is stated that

${\bf NP ^{PP}} \subseteq {\bf P^{\#P^{[1]}}} $ if and only if ${\bf CH} = {\bf P^{\#P^{[1]}}} $ if and only if ${\bf FP ^{CH}} \subseteq {\bf FP^{\#P^{[1]}}} $.

> **Comments:**
> **username_2**: You also need that P^#P = P^#P[1] (proven in Toda's paper Simple characterizations of P(#P) and complete problems) to get the conclusion that NP^PP = P^PP implies that CH collapses.  
> **username_0**: @Tayfun: I cannot apply your argumentation for the collapse of the CH to my initial question, since as Lance pointed out, we additionally need P^#P = P^#P[1].  
> **username_0**: @Lance: I am reading your answer as P^#P = P^#P[1]. This confuses me even more, although it would fix the argumentation of Tayfun.  
> **username_0**: It would be awesome, if you could provide me just a tiny bit more of information: 1) Which of Toda's papers? 2) Which result in that paper? 3) With "my answer" you refer to proposition 2.1 in the paper of Ogihara, Toda, Watanabe, Thierauf? thanks a lot...  
> **username_1**: @DennisWeyland What Lance is referring to is in Toda's Paper "Simple Characterizations of P(#P) and complete problems" Theorem 3.2., which states that ${\bf FP ^{\#P^{NP}}} \subseteq {\bf FP^{FP^{\#P_{[1]}}}} \subseteq {\bf FP ^{\#P}}$.  

---

