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


  • 1
    $\begingroup$ 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$) $\endgroup$ – Ramprasad Oct 30 '10 at 8:14
  • 3
    $\begingroup$ 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.) $\endgroup$ – M.S. Dousti Oct 30 '10 at 10:10
  • 2
    $\begingroup$ 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.) $\endgroup$ – Boaz Barak Nov 1 '10 at 2:40
  • 2
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Nov 1 '10 at 3:28
  • 1
    $\begingroup$ 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 meta.cstheory.stackexchange.com/questions/300/…, meta.cstheory.stackexchange.com/questions/300/…. $\endgroup$ – Tsuyoshi Ito Nov 18 '10 at 1:40

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

  • 2
    $\begingroup$ Welcome to CSTheory.SE, @Bin Fu! :) $\endgroup$ – Daniel Apon Feb 1 '11 at 17:20
  • $\begingroup$ Or maybe you were here before, but welcome anyway! ;) $\endgroup$ – Daniel Apon Feb 1 '11 at 17:28
  • 1
    $\begingroup$ Thanks, Daniel Apon. It is known that PH^{Parity P} collapses. It will be very interesting if one can prove PH^{#P} collapses. $\endgroup$ – Bin Fu Feb 2 '11 at 16:27
  • $\begingroup$ Interesting, could you provide a reference for $PH^{\#P}$ and the problem of its collapse, please? $\endgroup$ – neophyte Jun 2 '15 at 9:03

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.

  • $\begingroup$ 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? $\endgroup$ – Tsuyoshi Ito Nov 19 '10 at 22:51
  • $\begingroup$ @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. $\endgroup$ – Mike Chen Nov 19 '10 at 23:35
  • 1
    $\begingroup$ “The polynomial hierarchy collapses” does not necessarily mean P=NP, and “the counting hierarchy collapses” does not necessarily mean PP=PP^PP. $\endgroup$ – Tsuyoshi Ito Nov 20 '10 at 2:01
  • 2
    $\begingroup$ In addition, P=NP does not imply P^#P=NP^#P as far as I know (but I may be missing something). $\endgroup$ – Tsuyoshi Ito Nov 20 '10 at 3:09
  • $\begingroup$ 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. $\endgroup$ – Derrick Stolee Feb 1 '11 at 17:48

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.