Statut de PP-complétude de MAJ3SAT

QUESTION COURTE: MAJ-3CNF est-il un problème PP-complet avec plusieurs réductions?

VERSION PLUS LONGUE: Il est bien connu que MAJSAT (décider si la majorité des affectations de phrase propositionnelle satisfont la phrase) est PP-complet sous plusieurs réductions et #SAT est # P-complet sous réductions parcimonieuses. Il est également évident que # 3CNF (c'est-à-dire, #SAT limité aux formules 3-CNF) est # P-complet, car la réduction Cook-Levin est parcimonieuse et produit un 3-CNF (cette réduction est en fait utilisée dans le livre de Papadimitriou pour show # P-exhausteness of #SAT).

Il semble qu'un argument similaire devrait prouver que MAJ-3CNF est PP-complet sous plusieurs réductions (MAJ-kCNF est MAJSAT limité aux formules kCNF; c'est-à-dire que chaque clause a k littéraux).

Cependant, dans une présentation de Bailey, Dalmau et Kolaitis, "Phase Transitions of PP-Complete Satisfiability Problems", les auteurs mentionnent que "MAJ3SAT n'est pas connu pour être PP-Complete" (présentation à https: //users.soe.ucsc .edu / ~ kolaitis / conversations / ppphase4.ppt ). Cette phrase ne semble pas apparaître dans leurs articles connexes, seulement dans leurs présentations.

Questions: La preuve que # 3CNF est # P-complete peut-elle être adaptée pour prouver que MAJ3CNF est PP-complete? Compte tenu de la déclaration de Bailey et al., Il ne semble pas; si la preuve ne porte pas, alors: Existe-t-il une preuve que MAJ-3CNF est PP-complet? Sinon, y a-t-il une certaine intuition quant à la différence entre PP et #P par rapport à ce résultat?

RÉPONSE COURTE:
On ne sait pas si est un problème -complete sous plusieurs réductions.$\mathsf{MAJ3CNF}$$\mathsf{PP}$

LONGUE RÉPONSE:
Tout d'abord, vous faites référence à Bailey, Dalmau et Kolaitis, et à leur travail sur les "Transitions de phase des problèmes de satisfaction complétés par "$\mathsf{PP}$ dans votre question. Permettez-moi de les citer:

'Il convient également de noter que, bien que soit -complet, on ne sait pas s'il existe un entier , tel que est -complete. '$\mathsf{MAJORITY \ SAT}$$\mathsf{PP}$$k \geq 3$$\mathsf{MAJORITY}$ $\mathsf{kSAT}$$\mathsf{PP}$

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

Il est en effet exact que la réduction de Cook-Levin est parcimonieuse et produit un 3CNF à partir d'un CNF donné. Comme est -complet, il s'ensuit immédiatement que est également -complet sous des réductions parcimonieuses. Cependant, comme déjà souligné dans un commentaire, les réductions parcimonieuses ne préservent pas la majorité. Ces réductions introduisent des variables auxiliaires pour réduire la taille des clauses, mais à leur tour, ces variables auxiliaires augmentent le nombre total d'affectations. Par exemple, considérons le 4CNF qui consiste en une seule clause:$\mathsf{\#CNF}$$\mathsf{\#P}$$\mathsf{\#3CNF}$$\mathsf{\#P}$

$\phi = (x_1 \vee x_2 \vee x_3 \vee x_4)$

qui se transforme en

$\phi'=(x_1 \vee x_2 \vee y) \wedge (y \leftrightarrow (x_3 \vee x_4))$

en utilisant la variable auxiliaire et enfin au 3CNF$y$

$\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).$

Cette transformation préserve clairement le nombre de modèles, mais il est facile de voir que la majorité n'est pas conservée. a 15 affectations satisfaisantes sur 16 affectations tandis que a 15 affectations satisfaisantes sur 32 affectations. Dans le premier cas, la satisfiabilité majoritaire est vraie alors que dans le second cas la satisfiabilité majoritaire ne tient pas.$\phi$$\psi$

Par conséquent, NON, la preuve que # 3CNF est -complète ne peut pas être adaptée pour prouver que est -complète? Il reste ouvert si est un problème -complete sous plusieurs réductions.$\mathsf{\#P}$$\mathsf{MAJ3CNF}$$\mathsf{PP}$$\mathsf{MAJ3CNF}$$\mathsf{PP}$

# $\mathsf{MAJ3CNF}$ ne donne pas beaucoup d'informations sur les différences de et . En fait, la variante de décision décision de , disons , est définie comme suit: étant donné un CNF et un nombre , décidez si a au moins satisfaisant missions. Notez que pour , nous ne nous soucions pas de la majorité. Ainsi, nous pouvons transformer n'importe quel CNF en 3CNF en utilisant une réduction parcimonieuse, ce qui prouve que est -complet sous plusieurs réductions.$\mathsf{\#P}$# 3 C N F D # 3 C N F ϕ m ≥ 0 ϕ m D # 3 C N F D # 3 C N F P P M A J 3 C N F D # 3 C N $\mathsf{PP}$$\mathsf{\#3CNF}$$\mathsf{D\#3CNF}$$\phi$$m \geq 0$$\phi$$m$$\mathsf{D\#3CNF}$$\mathsf{D\#3CNF}$$\mathsf{PP}$$\mathsf{MAJ3CNF}$ est tout simplement un problème différent de .$\mathsf{D\#3CNF}$