6

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.

Dennis Weyland
  • 306
  • 1
  • 6
  • Check out the paper "Satanic notations: Counting Classes beyond #P and Other Definitional Adventures" by Hemaspaandra and Vollmer – Tayfun Pay Dec 06 '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? – Dennis Weyland Dec 07 '13 at 00: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 – Tayfun Pay Dec 07 '13 at 01:01
  • 1
    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 Dec 07 '13 at 01:23
  • Why don't you cite that paper? – Tayfun Pay Dec 07 '13 at 01:52
  • 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 Dec 07 '13 at 02:02

1 Answers1

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

Tayfun Pay
  • 2,598
  • 2
  • 18
  • 45
  • 3
    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 Dec 08 '13 at 21:33
  • @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 Dec 08 '13 at 23:56
  • @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 Dec 08 '13 at 23:57
  • 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 Dec 10 '13 at 03:03
  • @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 Dec 21 '13 at 22:09