10
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Ryan Williams Sep 26 '16 at 20:48
  • $\begingroup$ @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... $\endgroup$ – Tayfun Pay Feb 11 '17 at 18:47
  • $\begingroup$ 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 scholar.google.com/… $\endgroup$ – Ryan Williams Feb 11 '17 at 19:27
  • $\begingroup$ @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... $\endgroup$ – Tayfun Pay Feb 11 '17 at 20:09
  • $\begingroup$ @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. $\endgroup$ – Tayfun Pay Feb 11 '17 at 20:12
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @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? $\endgroup$ – T.... Aug 25 at 16:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.