<p>We know that <a href="http://en.wikipedia.org/wiki/PP_%28complexity%29" rel="nofollow">$\mathsf{PP}$</a> is equal in power to <a href="http://en.wikipedia.org/wiki/Sharp-P" rel="nofollow">$\#\mathsf{P}$</a> in the sense that $\mathsf{P^{PP}} = \mathsf{P}^{\#\mathsf{P}}$ (see the <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aP#psharpp" rel="nofollow">Complexity Zoo</a> entry). The similar question about <a href="http://en.wikipedia.org/wiki/Parity_P" rel="nofollow">$\mathsf{\oplus P}$</a>'s power is not known.</p>

<p>We can think of $\mathsf{PP}$ as giving the most significant bit of the number of solutions and $\mathsf{\oplus P}$ as giving the least significant bit. This question is about the underlying reason for their difference. Lets use $\#M$ to denote the number of solutions for $M$ on a given input $x$, i.e. $\#M = \{y : (x,y)\in M\}$.</p>

<p>For two given formulas $f$ and $g$, we can easily create formulas such that the number of their solutions will be $\#f+1$, $\#f + \#g$, $\#f \cdot \#g$, and $\#f \mod 2$. Is the problem about finding a formula which has $\#f \ / \ 2$ solutions?</p>

<p>If this is the case, has there been any work in this area? What is the state of the art?</p>

CC BY-SA 3.0
2011-10-29T09:29:23.027Z
Hi. Please read the [FAQ](http://cstheory.stackexchange.com/faq) and [the items regarding how to ask a good question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question), in particular [tell us why you care about the questions](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/306#306). You have asked [a considerable number of questions on MO](http://meta.mathoverflow.net/discussion/1164/recent-questions-in-complexity-theory/) which are left unanswered and doesn't seem to be of use to anyone else.
Kaveh
CC BY-SA 3.0
2011-10-29T09:34:26.593Z
Please try to make your questions on cstheory useful and interesting also for others, and asks only questions that you are *seriously* thinking about, don't ask questions which you don't care if they don't get answered.
Kaveh
CC BY-SA 3.0
2011-10-29T10:16:13.890Z
ps: I think your questions just need a little bit more effort on your part to be interesting to others and receive answers. I will try to help you with this one, feel free to roll back or edit if you don't like my edits or I misunderstand the question.
Kaveh
CC BY-SA 3.0
2011-10-29T11:58:39.300Z
@Kaveh: Your edit in revision 2 added a claim that given a Boolean formula f, one can easily construct a Boolean formula with the number of solutions equal to (#f mod 2), but I cannot follow this.  How can it be done?
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-29T12:12:31.840Z
@Tsuyoshi, yes, you are right. I did notice that when I was checking my edit with the original question. My understanding is that it is with a $\oplus\mathsf{P}$ oracle. The original wasn't very clear so I might have misunderstood, it had "For two given formulas f and g, we can easily add two parities". We can wait for the OP to check my edit and clarify the point, but do you have a different interpretation of that sentence?
Kaveh
CC BY-SA 3.0
2011-10-29T12:36:23.280Z
@Anonymous, I want to suggest once more that you register your account even if you want to remain anonymous. For registration you only need an OpenID (which you can get easily from [SE](https://openid.stackexchange.com/), [MyOpenID](http://myopenid.com/) or other providers like Google) so you can login back into your account. Registration will allow you to edit your posts, comment and reply to comments in future.
Kaveh
CC BY-SA 3.0
2011-10-29T16:32:02.937Z
What is the question?
Tayfun Pay
CC BY-SA 3.0
2011-10-29T20:51:02.920Z
Chapter 5 of the Complexity Theory Companion might be helpful.
Markus Bläser
CC BY-SA 3.0
2011-10-29T23:29:26.170Z
@Kaveh: I do not know what “we can easily add two parities” means.  Now I see how you interpreted it, but I am not sure if that is what the asker meant.  If that is intended, then “using ⊕P oracle” should be made explicit to avoid the confusion.
Tsuyoshi Ito
<cc.complexity-theory>
Open Problem Concerning Parity Sat
Anonymous Coward
# Open Problem Concerning Parity Sat

(Asked by: username_0 on 2011-10-29)

We know that [$\mathsf{PP}$](http://en.wikipedia.org/wiki/PP_%28complexity%29) is equal in power to [$\#\mathsf{P}$](http://en.wikipedia.org/wiki/Sharp-P) in the sense that $\mathsf{P^{PP}} = \mathsf{P}^{\#\mathsf{P}}$ (see the [Complexity Zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aP#psharpp) entry). The similar question about [$\mathsf{\oplus P}$](http://en.wikipedia.org/wiki/Parity_P)'s power is not known.

We can think of $\mathsf{PP}$ as giving the most significant bit of the number of solutions and $\mathsf{\oplus P}$ as giving the least significant bit. This question is about the underlying reason for their difference. Lets use $\#M$ to denote the number of solutions for $M$ on a given input $x$, i.e. $\#M = \{y : (x,y)\in M\}$.

For two given formulas $f$ and $g$, we can easily create formulas such that the number of their solutions will be $\#f+1$, $\#f + \#g$, $\#f \cdot \#g$, and $\#f \mod 2$. Is the problem about finding a formula which has $\#f \ / \ 2$ solutions?

If this is the case, has there been any work in this area? What is the state of the art?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: Hi. Please read the [FAQ](http://cstheory.stackexchange.com/faq) and [the items regarding how to ask a good question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question), in particular [tell us why you care about the questions](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/306#306). You have asked [a considerable number of questions on MO](http://meta.mathoverflow.net/discussion/1164/recent-questions-in-complexity-theory/) which are left unanswered and doesn't seem to be of use to anyone else.  
> **username_1**: Please try to make your questions on cstheory useful and interesting also for others, and asks only questions that you are *seriously* thinking about, don't ask questions which you don't care if they don't get answered.  
> **username_1**: ps: I think your questions just need a little bit more effort on your part to be interesting to others and receive answers. I will try to help you with this one, feel free to roll back or edit if you don't like my edits or I misunderstand the question.  
> **username_2**: @Kaveh: Your edit in revision 2 added a claim that given a Boolean formula f, one can easily construct a Boolean formula with the number of solutions equal to (#f mod 2), but I cannot follow this.  How can it be done?  
> **username_1**: @Tsuyoshi, yes, you are right. I did notice that when I was checking my edit with the original question. My understanding is that it is with a $\oplus\mathsf{P}$ oracle. The original wasn't very clear so I might have misunderstood, it had "For two given formulas f and g, we can easily add two parities". We can wait for the OP to check my edit and clarify the point, but do you have a different interpretation of that sentence?  
> **username_1**: @Anonymous, I want to suggest once more that you register your account even if you want to remain anonymous. For registration you only need an OpenID (which you can get easily from [SE](https://openid.stackexchange.com/), [MyOpenID](http://myopenid.com/) or other providers like Google) so you can login back into your account. Registration will allow you to edit your posts, comment and reply to comments in future.  
> **username_3**: What is the question?  
> **username_4**: Chapter 5 of the Complexity Theory Companion might be helpful.  
> **username_2**: @Kaveh: I do not know what “we can easily add two parities” means.  Now I see how you interpreted it, but I am not sure if that is what the asker meant.  If that is intended, then “using ⊕P oracle” should be made explicit to avoid the confusion.  

---

## 0 answers

