Status der PP-Vollständigkeit von MAJ3SAT

KURZE FRAGE: Ist MAJ-3CNF ein PP-vollständiges Problem bei vielen Reduzierungen?

LÄNGERE VERSION: Es ist bekannt, dass MAJSAT (Entscheidung, ob die Mehrheit der Zuweisungen des Satzsatzes dem Satz entspricht) unter vielen Reduzierungen PP-vollständig und #SAT unter sparsamen Reduzierungen # P-vollständig ist. Es ist auch offensichtlich, dass # 3CNF (dh #SAT, beschränkt auf 3-CNF-Formeln) # P-vollständig ist, da die Cook-Levin-Reduktion sparsam ist und einen 3-CNF erzeugt (diese Reduktion wird tatsächlich in Papadimitrious Buch verwendet) zeige # P-Vollständigkeit von #SAT).

Es scheint, dass ein ähnliches Argument beweisen sollte, dass MAJ-3CNF unter vielen Reduktionen PP-vollständig ist (MAJ-kCNF ist MAJSAT, das auf kCNF-Formeln beschränkt ist; das heißt, jede Klausel hat k Literale).

In einer Präsentation von Bailey, Dalmau und Kolaitis, "Phasenübergänge von PP-vollständigen Erfüllbarkeitsproblemen", erwähnen die Autoren jedoch, dass "MAJ3SAT nicht als PP-vollständig bekannt ist" (Präsentation unter https: //users.soe.ucsc .edu / ~ kolaitis / gespräche / ppphase4.ppt ). Dieser Satz scheint nicht in verwandten Artikeln zu erscheinen, sondern nur in ihren Präsentationen.

Fragen: Kann der Beweis, dass # 3CNF # P-vollständig ist, tatsächlich angepasst werden, um zu beweisen, dass MAJ3CNF PP-vollständig ist? Angesichts der Aussage von Bailey et al. Scheint es nicht; Wenn der Beweis nicht vorliegt, dann: Gibt es einen Beweis dafür, dass MAJ-3CNF PP-vollständig ist? Wenn nicht, gibt es eine gewisse Intuition hinsichtlich des Unterschieds zwischen PP und #P in Bezug auf dieses Ergebnis?

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

was verwandelt wird in

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