Given a $CIRCUITSAT$ instance $\varphi(n)$ in $n$ variables and a fixed $k>1$ the problem of deciding if the number of satisfying witnesses is $2^n\big(1-\frac1k\big)$ or $\frac{2^n}k$ is $PP$ complete.

Is there a problem related to the above which is in $BPP$?

  • 5
    $\begingroup$ For fixed constant k > 2 this a Promise-BPP problem. Pretty doubtful it's PP complete. $\endgroup$ – Ryan Williams Jul 22 at 2:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.