Suppose $A$ is any #P-complete problem. Now, $A$ is modified to obtain a decision problem $A'$ not by asking whether there is a solution but whether at least half of the potential solutions are actually true solutions. Question: Is $A'$ PP-complete?

This works if $A$ is #Sat, since MajSat is PP-complete. My approach so far: If $A$ is #P-complete, then there is a reduction from #Sat. So it should be possible to adapt this reduction to obtain a reduction from MajSat to $A'$. However, I ran into the problem that the reduction from #Sat to $A$ often requires a Turing (or Cook) reduction and it seemed far from clear how to obtain a many-one reduction from it.


1 Answer 1


Not necessary. Imagine the following Fake-#SAT problem: possible solutions are extended by one bit, and all vectors with this bit set are solutions. That is, the number of satisfying assignments for the new problem is $2^n+f$, where $f$ is the number of satisfying assignments for the original #SAT problem ($0\le f\le 2^n$).

The problem remains #P-complete; however, the corresponding "majority" problem (formulates as $\ge$ vs $<$) has always the answer "yes".


Your Answer

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