12

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

Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
Mike Chen
  • 709
  • 4
  • 10
  • 1
    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$) – Ramprasad Oct 30 '10 at 08:14
  • @Ramprasad: Exactly – Mike Chen Oct 30 '10 at 08:25
  • 3
    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.) – Sadeq Dousti Oct 30 '10 at 10:10
  • @Sadeq: I think you are right. But the problem is we don't know which containment is strict. 3 & 4 may be more challenging. – Mike Chen Nov 01 '10 at 01:17
  • 2
    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.) – Boaz Barak Nov 01 '10 at 02:40
  • 2
    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. – Robin Kothari Nov 01 '10 at 03:28
  • I read revision 7. What do you mean by FP? If it refers to the class of polynomial-time computable functions, you cannot compare NP^#P to FP^#P because NP^#P is a class of decision problems and FP^#P is a class of functions (type error!). – Tsuyoshi Ito Nov 18 '10 at 01:22
  • @Tsuyoshi: My mistake, fixed now. – Mike Chen Nov 18 '10 at 01:33
  • 1
    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 http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/304#304, http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/306#306. – Tsuyoshi Ito Nov 18 '10 at 01:40
  • 1
    By the way, I have to point out that most part of the quesiton looks like homework to me, although if it is, it is stated in a deliberately confusing way. – Tsuyoshi Ito Nov 18 '10 at 01:49
  • @Tsuyoshi: Thank you for your comments. To be honest, I am beginner in Computational complexity. Sometimes, I feel confused when reading complexity books. Toda's theorem points out $PH\subseteq P^{#P}=P^{PP}$, but it doesn't say anything about $NP^{#P}$ and $coNP^{#P}$, which to my mind seem to be equal. Plus, I almost can't find any literatures about $NP^{#P}$ and $coNP^{#P}$. Anyways, sorry for the confusions and thank you again for your comments. – Mike Chen Nov 18 '10 at 04:24
  • 1
    I read revision 9. (1) I think that the question is becoming interesting. Thank you for revising the question. And I hope that other people who answered the deleted part of the question are also fine with it (my guess is that that is why people posted their answers as comments, although I am not completely sure). (2) Can you clarify what you mean by “PP is neither a PSPACE-complete language nor a deterministic polynomial time language”? Needless to say, whether PP=PSPACE and whether P=PP are currently both unknown. (Moreover, PP is a class, not a language!) – Tsuyoshi Ito Nov 18 '10 at 12:40
  • 1
    @Tsuyoshi: I second that ;) I would correct the sentence you mentioned as: “assuming PP neither equals PSPACE nor P, is it true that...” – Sadeq Dousti Nov 18 '10 at 13:08

2 Answers2

12

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

Hsien-Chih Chang 張顯之
  • 7,638
  • 4
  • 44
  • 83
Bin Fu
  • 674
  • 4
  • 8
0

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.

Mike Chen
  • 709
  • 4
  • 10
  • 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? – Tsuyoshi Ito Nov 19 '10 at 22:51
  • @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. – Mike Chen Nov 19 '10 at 23:35
  • 2
    “The polynomial hierarchy collapses” does not necessarily mean P=NP, and “the counting hierarchy collapses” does not necessarily mean PP=PP^PP. – Tsuyoshi Ito Nov 20 '10 at 02:01
  • 3
    In addition, P=NP does not imply P^#P=NP^#P as far as I know (but I may be missing something). – Tsuyoshi Ito Nov 20 '10 at 03:09
  • 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. – Derrick Stolee Feb 01 '11 at 17:48
  • I would replace #P with PP and then you can definitely see that P^PP does not equal P^NP. Even if P=NP then you do not know if that equality will absorb PP into P as well. – Tayfun Pay Mar 27 '13 at 20:17