Status der PP-Vollständigkeit von MAJ3SAT

10

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?

Fabio Cozman
quelle
4
Die typische Reduzierung von CircuitSAT auf 3sat funktioniert nicht, da viele neue Variablen eingeführt werden. Während Sie also möglicherweise 2 ^ (n-1) + 1 hatten, die Zuordnungen zu einer bestimmten Schaltung mit n Eingängen erfüllen, und Sie so viele für die 3sat-Instanz haben, ist die Anzahl der Vars in der 3cnf-Instanz viel größer als n, so dass diese Zahl nicht mehr "die Mehrheit der befriedigenden Aufgaben" ist. Beachten Sie, dass Maj-3sat immer noch mindestens NP-hart ist, da Sie viele Dummy-Aufgaben hinzufügen können.
Ryan Williams
@RyanWilliams Wie wäre es, wenn wir diese 3CNF-Instanz nehmen, sie negieren und eine 3DNF-Instanz erhalten (die Negation dauert viel Zeit und wenn Sie einen CNF-Ausdruck negieren, erhalten Sie einen DNF-Ausdruck). Dann hatte die ursprüngliche CNF-Instanz mehr als (2 ^ (n-1)) erfüllende Wahrheitszuweisungen, wenn und nur wenn die 3DNF-Instanz mehr als (2 ^ ((n + K) -1) erfüllende Wahrheitszuweisungen hat, wobei K die ist Anzahl zusätzlicher Variablen ...
Tayfun Pay
Das Konvertieren von cnf in dnf dauert im Allgemeinen nicht lange. Schnelle Überprüfung der geistigen Gesundheit: Wenn dies der Fall ist, ist P = NP ... komplexere Prüfung: Es gibt cnfs von Poly (n) -Klauseln, deren minimale äquivalente dnfs exp viele Klauseln haben. Siehe zum Beispiel Scholar.google.com/…
Ryan Williams
@ RyanWilliams 1) Das Negieren eines Booleschen Ausdrucks dauert viel Zeit. 2) Wenn Sie einen CNF negieren, erhalten Sie einen DNF und umgekehrt. Am wichtigsten ist, dass das Negieren eines CNF in Polynomzeit und das Erhalten eines DNF als Gegenleistung die Komplexität dieses Problems nicht ändert. Sie müssten eine fälschende Wahrheitszuweisung für die negierte CNF-Formel finden, die jetzt eine DNF-Formel ist. Es ist NP-Complete, eine fälschende Wahrheitszuweisung für eine DNF-Formel zu finden ...
Tayfun Pay
@ RyanWilliams Ich kenne die Werke, die Sie zitiert haben. Sie erhalten jedoch einen DNF-Ausdruck, wenn Sie einen CNF-Ausdruck negieren. Und das braucht Polynomzeit in Bezug auf die Länge der Eingabe.
Tayfun Pay

Antworten:

1


MAJ3CNFPP



PP

MAJORITY SATPPk3MAJORITY kSATPP

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

#CNF#P#3CNF#P

ϕ=(x1x2x3x4)

was verwandelt wird in

ϕ=(x1x2y)(y(x3x4))

y

ψ=(x1x2y)(¬yx3x4)(y¬x3)(y¬x4).

ϕψ

#PMAJ3CNFPPMAJ3CNFPP

MAJ3CNF#PPP#3CNFD#3CNFϕm0ϕmD#3CNFD#3CNFPPMAJ3CNFD#3CNF

Hey Hey Hey
quelle
3SATP3SAT