Status de preenchimento de PP de MAJ3SAT

BREVE PERGUNTA: O MAJ-3CNF é um problema de PP completo com muitas reduções?

VERSÃO MAIS LONGA: É sabido que o MAJSAT (decidindo se a maioria das atribuições da sentença proposicional satisfaz a sentença) é completo em PP com muitas reduções de uma e #SAT é # P completo com reduções parcimoniosas. Também é aparente que # 3CNF (ou seja, #SAT restrito a fórmulas de 3-CNF) é # P-completo, porque a redução de Cook-Levin é parcimoniosa e produz um 3-CNF (essa redução é realmente usada no livro de Papadimitriou para mostre # P-completeness de #SAT).

Parece que um argumento semelhante deve provar que o MAJ-3CNF é completo em PP sob várias reduções (o MAJ-kCNF é MAJSAT restrito às fórmulas do kCNF; ou seja, cada cláusula tem k literais).

No entanto, em uma apresentação de Bailey, Dalmau e Kolaitis, "Transições de fase de problemas de satisfação do PP-Complete", os autores mencionam que "o MAJ3SAT não é conhecido como PP-Complete" (apresentação em https: //users.soe.ucsc .edu / ~ kolaitis / palestras / ppphase4.ppt ). Esta frase parece não aparecer em seus trabalhos relacionados, apenas em suas apresentações.

Perguntas: A prova de que # 3CNF é # P-complete pode realmente ser adaptada para provar que o MAJ3CNF é PP-complete? Dada a declaração de Bailey et al., Parece que não; se a prova não for válida, então: Existe uma prova de que o MAJ-3CNF está completo com PP? Caso contrário, existe alguma intuição quanto à diferença entre PP e #P em relação a esse resultado?

$\mathsf{MAJ3CNF}$$\mathsf{PP}$

$\mathsf{PP}$

$\mathsf{MAJORITY \ SAT}$$\mathsf{PP}$$k \geq 3$$\mathsf{MAJORITY}$ $\mathsf{kSAT}$$\mathsf{PP}$

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

$\mathsf{\#CNF}$$\mathsf{\#P}$$\mathsf{\#3CNF}$$\mathsf{\#P}$

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

que é transformado em

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

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

$\phi$$\psi$

$\mathsf{\#P}$$\mathsf{MAJ3CNF}$$\mathsf{PP}$$\mathsf{MAJ3CNF}$$\mathsf{PP}$

$\mathsf{MAJ3CNF}$$\mathsf{\#P}$$\mathsf{PP}$$\mathsf{\#3CNF}$$\mathsf{D\#3CNF}$$\phi$$m \geq 0$$\phi$$m$$\mathsf{D\#3CNF}$$\mathsf{D\#3CNF}$$\mathsf{PP}$$\mathsf{MAJ3CNF}$$\mathsf{D\#3CNF}$