<p>Hopefully the following paper finally resolves this question: it says that MAJORITY 3SAT is in polynomial time. (And it proves a bunch of other unexpected results on related problems.)</p>
<p><a href="https://arxiv.org/abs/2107.02748" rel="noreferrer">https://arxiv.org/abs/2107.02748</a></p>

CC BY-SA 4.0
2021-07-08T18:48:48.693Z
2021-07-08T18:48:48.693Z
Ryan Williams
<p>SHORT ANSWER:<br>
It is unknown whether $\mathsf{MAJ3CNF}$ is a $\mathsf{PP}$-complete problem under many-one reductions. </p>

<hr>

<p>LONG ANSWER:<br>
First of all, you refer to Bailey, Dalmau and Kolaitis, and their work on <em>"Phase Transitions of $\mathsf{PP}$-complete Satisfiability Problems"</em> in your question. Let me quote them:</p>

<p><em>'It is also worth noting that, although $\mathsf{MAJORITY \ SAT}$ is  $\mathsf{PP}$-complete, it is not known whether there is an integer $k \geq 3$, such that $\mathsf{MAJORITY}$ $\mathsf{kSAT}$ is $\mathsf{PP}$-complete.'</em></p>

<p>[<a href="http://www.sciencedirect.com/science/article/pii/S0166218X06004665" rel="nofollow noreferrer">http://www.sciencedirect.com/science/article/pii/S0166218X06004665</a> ]</p>

<p>It is, indeed, correct that Cook-Levin reduction is parsimonious and produces a 3CNF from a given CNF. As $\mathsf{\#CNF}$ is $\mathsf{\#P}$-complete, it immediately follows that $\mathsf{\#3CNF}$ is also $\mathsf{\#P}$-complete under parsimonious reductions. However, as already pointed in a comment, parsimonious reductions do not preserve majority. These reductions introduce auxiliary variables to reduce the size of the clauses, but in turn, these auxiliary variables increase the total number of assignments. For instance, consider the 4CNF which consists of a single clause:</p>

<p>$
\phi = (x_1 \vee x_2 \vee x_3 \vee x_4)
$</p>

<p>which is transformed into</p>

<p>$
\phi'=(x_1 \vee x_2 \vee y) \wedge (y \leftrightarrow (x_3 \vee x_4)) 
$</p>

<p>using the auxiliary variable $y$ and finally to the 3CNF</p>

<p>$
\psi= (x_1 \vee x_2 \vee y) \wedge (\neg y \vee x_3 \vee x_4) \wedge (y \vee \neg x_3 ) \wedge (y \vee \neg x_4). 
$</p>

<p>This transformation clearly preserves the model count, but it is easy to see that the majority is not preserved. $\phi$ has 15 satisfying assignments out of 16 assignments whereas $\psi$ has 15 satisfying assignments out of 32 assignments. In the former, majority satisfiability holds whereas in the latter  majority satisfiability does not hold.</p>

<p>Therefore, NO, the proof that #3CNF is $\mathsf{\#P}$-complete can not be adapted to prove that $\mathsf{MAJ3CNF}$ is $\mathsf{PP}$-complete? It remains open whether $\mathsf{MAJ3CNF}$ is a $\mathsf{PP}$-complete problem under many-one reductions. </p>

<p>$\mathsf{MAJ3CNF}$ does not give much of an insight between the differences of $\mathsf{\#P}$ and $\mathsf{PP}$. Actually decision decision variant of $\mathsf{\#3CNF}$, say $\mathsf{D\#3CNF}$, is defined as follows: given a CNF $\phi$ and a number $m \geq 0$, decide whether $\phi$ has at least $m$ satisfying assignments. Note that for $\mathsf{D\#3CNF}$, we do not care about majority. Thus, we can transform any CNF into 3CNF using a parsimonous reduction, which proves that $\mathsf{D\#3CNF}$ is $\mathsf{PP}$-complete under many-one reductions. $\mathsf{MAJ3CNF}$ is simply a different problem than $\mathsf{D\#3CNF}$.</p>

CC BY-SA 4.0
2019-08-25T16:50:07.393Z
@gamow How about parity of number of solutions of $3SAT$ formulas? Is it $\oplus\mathsf{P}$-complete and is there standard name for parity of number of solutions of $3SAT$ formulas?
Turbo
CC BY-SA 3.0
2017-02-07T09:47:17.687Z
2017-02-07T18:58:27.003Z
2017-02-07T18:58:27.003Z
Heyheyhey
<p>SHORT QUESTION: Is MAJ-3CNF a PP-complete problem under many-one reductions?</p>

<p>LONGER VERSION:
It is well-known that MAJSAT (deciding whether the majority of assignments of propositional sentence satisfy the sentence) is PP-complete under many-one reductions and #SAT is #P-complete under parsimonious reductions. It is also apparent that #3CNF (that is, #SAT restricted to 3-CNF formulas) is #P-complete, because the Cook-Levin reduction is parsimonious and produces a 3-CNF (this reduction is actually used in Papadimitriou's book to show #P-completeness of #SAT). </p>

<p>It seems that a similar argument should prove that MAJ-3CNF is PP-complete under many-one reductions (MAJ-kCNF is MAJSAT restricted to kCNF formulas; that is each clause has k literals). </p>

<p>However, in a presentation by Bailey, Dalmau and Kolaitis, "Phase Transitions of PP-Complete Satisfiability Problems", the authors mention that "MAJ3SAT is not known to be PP-Complete" (presentation at <a href="https://users.soe.ucsc.edu/~kolaitis/talks/ppphase4.ppt">https://users.soe.ucsc.edu/~kolaitis/talks/ppphase4.ppt</a>). This sentence does not seem to appear in their related papers, only in their presentations.</p>

<p>Questions: Can the proof that #3CNF is #P-complete be indeed adapted to prove that MAJ3CNF is PP-complete? Given the statement by Bailey et al., it seems not; if the proof does not carry, then: Is there a proof that MAJ-3CNF is PP-complete? If not, is there some intuition as to the difference between PP and #P with respect to this result? </p>

CC BY-SA 3.0
2016-09-26T20:48:20.317Z
The typical reduction from CircuitSAT to 3sat does not work because it introduces many new variables. So while you may have had 2^(n-1)+1 satisfying assignments to a given circuit with n inputs, and you will have that many for the 3sat instance, the number of vars in the 3cnf instance is much larger than n, so that number is no longer "a majority of satisfying assignments". Note that Maj-3sat is still at least NP hard, because you can add many dummy satisfying assignments.
Ryan Williams
CC BY-SA 3.0
2017-02-11T18:47:21.960Z
@RyanWilliams How about we take that 3CNF instance, negate it and get a 3DNF instance (negation takes poly-time and when you negate a CNF expression you get a DNF expression). Then the original CNF instance had more than (2^(n-1)) satisfying truth assignments if and only if the 3DNF instance has more than (2^((n+K)-1) satisfying truth assignments, where K is the number of additional variables...
Tayfun Pay
CC BY-SA 3.0
2017-02-11T19:27:07.427Z
Converting cnf into dnf does not take polytime in general. Quick sanity check: if it did then P=NP... more complex check: there are cnfs of poly(n) clauses whose minimum equivalent dnfs have exp many clauses. See for example https://scholar.google.com/scholar?biw=360&bih=560&um=1&ie=UTF-8&lr&cites=12609893241992964901
Ryan Williams
CC BY-SA 3.0
2017-02-11T20:09:51.650Z
@RyanWilliams  1) It takes poly time to negate a Boolean expression 2) When you negate a CNF you do get a DNF, and vice versa.  Most importantly, negating a CNF in polynomial time and getting a DNF in return does not change the complexity of that problem. You would need to find a falsifying truth assignment for the negated CNF formula, which is now a DNF formula. It is NP-Complete to find a falsifying truth assignment for a DNF formula...
Tayfun Pay
CC BY-SA 3.0
2017-02-11T20:12:48.577Z
@RyanWilliams I know the works you have cited.. However, you get a DNF expression when you negate a CNF expression. And that takes polynomial time with respect to the length of the input.
Tayfun Pay
CC BY-SA 3.0
2017-02-12T00:14:56.790Z
@RyanWilliams There is no theorem in that paper that states a given CNF of poly(n) size cannot be ${\bf negated}$ in polynomial time. I am ${\bf not}$ talking about converting a given CNF to a DNF or vice versa. I am talking about ${\bf negating}$ a given CNF. If you do not believe me, take a CNF and negate it and see what you get... You will get a DNF... And you can clearly do that in polynomial time. ${\bf HINT} $ Take a DNF Tautology and negate it! What do you get? A CNF Contradiction!... Both are Co-NP-Complete.
Tayfun Pay
CC BY-SA 3.0
2017-02-12T00:20:05.117Z
Sorry, I misunderstood your original comment. I don't see how the lower bound on assignments for the DNF follows, then.
Ryan Williams
CC BY-SA 3.0
2017-03-07T04:11:12.113Z
Irregardless, negating it reverses the truth and falsifying assignments to the given Boolean expression, but does not tell us if the original Boolean expression had more than half or not...
Tayfun Pay
CC BY-SA 4.0
2019-08-17T12:06:58.713Z
#P-completeness clearly does not imply PP-completeness. #2SAT is #P-complete, but MAJ2SAT is solvable in deterministic polynomial time.
rus9384
CC BY-SA 4.0
2021-05-30T03:05:32.697Z
For what it's worth, I am not sure why I wrote above that "Maj-3sat is still at least NP-hard"...
Ryan Williams
CC BY-SA 4.0
2021-07-07T11:17:54.363Z
@RyanWilliams Now that the news is out, it would seems most appropriate that you yourself write an answer updating us on the new status of MAJ3SAT. Or do I miss something?
Thomas Klimpel
<counting-complexity><complexity><probabilistic-complexity>
Status of PP-completeness of MAJ3SAT
Fabio Cozman
# Status of PP-completeness of MAJ3SAT

(Asked by: username_0 on 2016-09-26)

SHORT QUESTION: Is MAJ-3CNF a PP-complete problem under many-one reductions?

LONGER VERSION:
It is well-known that MAJSAT (deciding whether the majority of assignments of propositional sentence satisfy the sentence) is PP-complete under many-one reductions and #SAT is #P-complete under parsimonious reductions. It is also apparent that #3CNF (that is, #SAT restricted to 3-CNF formulas) is #P-complete, because the Cook-Levin reduction is parsimonious and produces a 3-CNF (this reduction is actually used in Papadimitriou's book to show #P-completeness of #SAT).

It seems that a similar argument should prove that MAJ-3CNF is PP-complete under many-one reductions (MAJ-kCNF is MAJSAT restricted to kCNF formulas; that is each clause has k literals).

However, in a presentation by Bailey, Dalmau and Kolaitis, "Phase Transitions of PP-Complete Satisfiability Problems", the authors mention that "MAJ3SAT is not known to be PP-Complete" (presentation at <https://users.soe.ucsc.edu/~kolaitis/talks/ppphase4.ppt>). This sentence does not seem to appear in their related papers, only in their presentations.

Questions: Can the proof that #3CNF is #P-complete be indeed adapted to prove that MAJ3CNF is PP-complete? Given the statement by Bailey et al., it seems not; if the proof does not carry, then: Is there a proof that MAJ-3CNF is PP-complete? If not, is there some intuition as to the difference between PP and #P with respect to this result?

**Tags:** counting-complexity, complexity, probabilistic-complexity
> **Comments:**
> **username_1**: The typical reduction from CircuitSAT to 3sat does not work because it introduces many new variables. So while you may have had 2^(n-1)+1 satisfying assignments to a given circuit with n inputs, and you will have that many for the 3sat instance, the number of vars in the 3cnf instance is much larger than n, so that number is no longer "a majority of satisfying assignments". Note that Maj-3sat is still at least NP hard, because you can add many dummy satisfying assignments.  
> **username_2**: @RyanWilliams How about we take that 3CNF instance, negate it and get a 3DNF instance (negation takes poly-time and when you negate a CNF expression you get a DNF expression). Then the original CNF instance had more than (2^(n-1)) satisfying truth assignments if and only if the 3DNF instance has more than (2^((n+K)-1) satisfying truth assignments, where K is the number of additional variables...  
> **username_1**: Converting cnf into dnf does not take polytime in general. Quick sanity check: if it did then P=NP... more complex check: there are cnfs of poly(n) clauses whose minimum equivalent dnfs have exp many clauses. See for example https://scholar.google.com/scholar?biw=360&bih=560&um=1&ie=UTF-8&lr&cites=12609893241992964901  
> **username_2**: @RyanWilliams  1) It takes poly time to negate a Boolean expression 2) When you negate a CNF you do get a DNF, and vice versa.  Most importantly, negating a CNF in polynomial time and getting a DNF in return does not change the complexity of that problem. You would need to find a falsifying truth assignment for the negated CNF formula, which is now a DNF formula. It is NP-Complete to find a falsifying truth assignment for a DNF formula...  
> **username_2**: @RyanWilliams I know the works you have cited.. However, you get a DNF expression when you negate a CNF expression. And that takes polynomial time with respect to the length of the input.  
> **username_2**: @RyanWilliams There is no theorem in that paper that states a given CNF of poly(n) size cannot be ${\bf negated}$ in polynomial time. I am ${\bf not}$ talking about converting a given CNF to a DNF or vice versa. I am talking about ${\bf negating}$ a given CNF. If you do not believe me, take a CNF and negate it and see what you get... You will get a DNF... And you can clearly do that in polynomial time. ${\bf HINT} $ Take a DNF Tautology and negate it! What do you get? A CNF Contradiction!... Both are Co-NP-Complete.  
> **username_1**: Sorry, I misunderstood your original comment. I don't see how the lower bound on assignments for the DNF follows, then.  
> **username_2**: Irregardless, negating it reverses the truth and falsifying assignments to the given Boolean expression, but does not tell us if the original Boolean expression had more than half or not...  
> **username_3**: #P-completeness clearly does not imply PP-completeness. #2SAT is #P-complete, but MAJ2SAT is solvable in deterministic polynomial time.  
> **username_1**: For what it's worth, I am not sure why I wrote above that "Maj-3sat is still at least NP-hard"...  
> **username_4**: @RyanWilliams Now that the news is out, it would seems most appropriate that you yourself write an answer updating us on the new status of MAJ3SAT. Or do I miss something?  

---

## 2 answers

### Answer by username_1 on 2021-07-08. Score: 20

Hopefully the following paper finally resolves this question: it says that MAJORITY 3SAT is in polynomial time. (And it proves a bunch of other unexpected results on related problems.)

<https://arxiv.org/abs/2107.02748>


---

### Answer by username_5 on 2017-02-07. Score: 2

SHORT ANSWER:  
It is unknown whether $\mathsf{MAJ3CNF}$ is a $\mathsf{PP}$-complete problem under many-one reductions.

---

LONG ANSWER:  
First of all, you refer to Bailey, Dalmau and Kolaitis, and their work on *"Phase Transitions of $\mathsf{PP}$-complete Satisfiability Problems"* in your question. Let me quote them:

*'It is also worth noting that, although $\mathsf{MAJORITY \ SAT}$ is $\mathsf{PP}$-complete, it is not known whether there is an integer $k \geq 3$, such that $\mathsf{MAJORITY}$ $\mathsf{kSAT}$ is $\mathsf{PP}$-complete.'*

[<http://www.sciencedirect.com/science/article/pii/S0166218X06004665> ]

It is, indeed, correct that Cook-Levin reduction is parsimonious and produces a 3CNF from a given CNF. As $\mathsf{\#CNF}$ is $\mathsf{\#P}$-complete, it immediately follows that $\mathsf{\#3CNF}$ is also $\mathsf{\#P}$-complete under parsimonious reductions. However, as already pointed in a comment, parsimonious reductions do not preserve majority. These reductions introduce auxiliary variables to reduce the size of the clauses, but in turn, these auxiliary variables increase the total number of assignments. For instance, consider the 4CNF which consists of a single clause:

$
\phi = (x\_1 \vee x\_2 \vee x\_3 \vee x\_4)
$

which is transformed into

$
\phi'=(x\_1 \vee x\_2 \vee y) \wedge (y \leftrightarrow (x\_3 \vee x\_4))
$

using the auxiliary variable $y$ and finally to the 3CNF

$
\psi= (x\_1 \vee x\_2 \vee y) \wedge (\neg y \vee x\_3 \vee x\_4) \wedge (y \vee \neg x\_3 ) \wedge (y \vee \neg x\_4).
$

This transformation clearly preserves the model count, but it is easy to see that the majority is not preserved. $\phi$ has 15 satisfying assignments out of 16 assignments whereas $\psi$ has 15 satisfying assignments out of 32 assignments. In the former, majority satisfiability holds whereas in the latter majority satisfiability does not hold.

Therefore, NO, the proof that #3CNF is $\mathsf{\#P}$-complete can not be adapted to prove that $\mathsf{MAJ3CNF}$ is $\mathsf{PP}$-complete? It remains open whether $\mathsf{MAJ3CNF}$ is a $\mathsf{PP}$-complete problem under many-one reductions.

$\mathsf{MAJ3CNF}$ does not give much of an insight between the differences of $\mathsf{\#P}$ and $\mathsf{PP}$. Actually decision decision variant of $\mathsf{\#3CNF}$, say $\mathsf{D\#3CNF}$, is defined as follows: given a CNF $\phi$ and a number $m \geq 0$, decide whether $\phi$ has at least $m$ satisfying assignments. Note that for $\mathsf{D\#3CNF}$, we do not care about majority. Thus, we can transform any CNF into 3CNF using a parsimonous reduction, which proves that $\mathsf{D\#3CNF}$ is $\mathsf{PP}$-complete under many-one reductions. $\mathsf{MAJ3CNF}$ is simply a different problem than $\mathsf{D\#3CNF}$.

> **Comments:**
> **username_6**: @gamow How about parity of number of solutions of $3SAT$ formulas? Is it $\oplus\mathsf{P}$-complete and is there standard name for parity of number of solutions of $3SAT$ formulas?  

---

