<p>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$).</p>

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

CC BY-SA 3.0
2015-04-14T09:22:26.613Z
2015-04-14T09:22:26.613Z
hirsch
<p>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? </p>

<p>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.</p>

<cc.complexity-theory><complexity-classes><counting-complexity><reductions><probabilistic-complexity>
#P- vs PP-Completeness
Oliver Witt
# #P- vs PP-Completeness

(Asked by: username_0 on 2015-04-14)

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.

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, reductions, probabilistic-complexity


---

## 1 answers

### Answer by username_1 on 2015-04-14. Score: 8 | Accepted answer

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".


---

