# Do we know whether P^#P = NP^#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).

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.

• Check out the paper "Satanic notations: Counting Classes beyond #P and Other Definitional Adventures" by Hemaspaandra and Vollmer Dec 6 '13 at 23:41
• 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? Dec 7 '13 at 0:44
• 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 Dec 7 '13 at 1:01
• 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. Dec 7 '13 at 1:23
• Why don't you cite that paper? Dec 7 '13 at 1:52

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]}}}$.
• @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}}$. Dec 21 '13 at 22:09