3
$\begingroup$

We know that $\mathsf{PP}$ is equal in power to $\#\mathsf{P}$ in the sense that $\mathsf{P^{PP}} = \mathsf{P}^{\#\mathsf{P}}$ (see the Complexity Zoo entry). The similar question about $\mathsf{\oplus 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?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Hi. Please read the FAQ and the items regarding how to ask a good question, in particular tell us why you care about the questions. You have asked a considerable number of questions on MO which are left unanswered and doesn't seem to be of use to anyone else. $\endgroup$
    – Kaveh
    Commented Oct 29, 2011 at 9:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Oct 29, 2011 at 9:34
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Oct 29, 2011 at 10:16
  • 1
    $\begingroup$ @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? $\endgroup$
    – Tsuyoshi Ito
    Commented Oct 29, 2011 at 11:58
  • 1
    $\begingroup$ @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, MyOpenID 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. $\endgroup$
    – Kaveh
    Commented Oct 29, 2011 at 12:36

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.