12
$\begingroup$

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

$coNP^{\#P}=NP^{\#P}=P^{\#P}$?

$\endgroup$
13
  • 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
    Commented Oct 30, 2010 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$ Commented Oct 30, 2010 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
    Commented Nov 1, 2010 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$ Commented Nov 1, 2010 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$ Commented Nov 18, 2010 at 1:40

2 Answers 2

12
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ Welcome to CSTheory.SE, @Bin Fu! :) $\endgroup$ Commented Feb 1, 2011 at 17:20
  • $\begingroup$ Or maybe you were here before, but welcome anyway! ;) $\endgroup$ Commented Feb 1, 2011 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
    Commented Feb 2, 2011 at 16:27
  • $\begingroup$ Interesting, could you provide a reference for $PH^{\#P}$ and the problem of its collapse, please? $\endgroup$
    – neophyte
    Commented Jun 2, 2015 at 9:03
0
$\begingroup$

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.

$\endgroup$
6
  • $\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$ Commented Nov 19, 2010 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
    Commented Nov 19, 2010 at 23:35
  • 2
    $\begingroup$ “The polynomial hierarchy collapses” does not necessarily mean P=NP, and “the counting hierarchy collapses” does not necessarily mean PP=PP^PP. $\endgroup$ Commented Nov 20, 2010 at 2:01
  • 3
    $\begingroup$ In addition, P=NP does not imply P^#P=NP^#P as far as I know (but I may be missing something). $\endgroup$ Commented Nov 20, 2010 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$ Commented Feb 1, 2011 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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