Status of PP-completeness of MAJ3SAT

Question

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?

Answer 1

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 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}$.