6
$\begingroup$

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.

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

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

$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 8 '13 at 21:33
  • $\begingroup$ @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]. $\endgroup$ Dec 8 '13 at 23:56
  • $\begingroup$ @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. $\endgroup$ Dec 8 '13 at 23:57
  • $\begingroup$ 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... $\endgroup$ Dec 10 '13 at 3:03
  • $\begingroup$ @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}}$. $\endgroup$
    – Tayfun Pay
    Dec 21 '13 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.