Status kompletności PP MAJ3SAT

KRÓTKIE PYTANIE: Czy MAJ-3CNF jest problemem kompletnym z PP przy wielu redukcjach?

DŁUŻSZA WERSJA: Dobrze wiadomo, że MAJSAT (decydujący, czy większość przypisań zdania zdaniowego spełnia zdanie) jest PP-kompletny przy wielu redukcjach jeden, a #SAT jest # P-kompletny przy redukcjach oszczędnych. Oczywiste jest również, że # 3CNF (czyli #SAT ograniczony do formuł 3-CNF) jest # P-ukończony, ponieważ redukcja Cooka-Levina jest skąpe i wytwarza 3-CNF (ta redukcja jest faktycznie używana w książce Papadimitriou do pokaż # P-kompletność #SAT).

Wydaje się, że podobny argument powinien udowodnić, że MAJ-3CNF jest kompletny z PP przy wielu redukcjach jeden (MAJ-kCNF jest MAJSAT ograniczony do formuł kCNF; to znaczy każda klauzula ma literały k).

Jednak w prezentacji Baileya, Dalmau i Kolaitisa, „Przejścia fazowe problemów z całkowitą satysfakcją z PP”, autorzy wspominają, że „MAJ3SAT nie jest znany z PP-Complete” (prezentacja na https: //users.soe.ucsc .edu / ~ kolaitis / talks / ppphase4.ppt ). To zdanie nie pojawia się w powiązanych artykułach, tylko w ich prezentacjach.

Pytania: Czy dowód, że # 3CNF jest # P-kompletny, może rzeczywiście zostać zaadaptowany, aby udowodnić, że MAJ3CNF jest kompletny z PP? Biorąc pod uwagę oświadczenie Bailey i wsp., Wydaje się, że nie; jeśli dowód nie zawiera, to: Czy istnieje dowód, że MAJ-3CNF jest kompletny z PP? Jeśli nie, to czy jest jakaś intuicja co do różnicy między PP a #P w odniesieniu do tego wyniku?

KRÓTKA ODPOWIEDŹ:
Nie wiadomo, czy jest problemem przy wielu redukcjach.P $\mathsf{MAJ3CNF}$$\mathsf{PP}$

DŁUGA ODPOWIEDŹ:
Po pierwsze, w swoim pytaniu odnosisz się do Baileya, Dalmau i Kolaitisa i ich pracy nad „Przejściami fazowymi -kompletnych problemów z satysfakcją”$\mathsf{PP}$ . Pozwólcie mi je zacytować:

„Warto również zauważyć, że chociaż jest -kompletny, nie wiadomo, czy istnieje liczba całkowita , taka że jest -kompletny. 'P P k ≥ 3 M A J O R I T Y k S A T P $\mathsf{MAJORITY \ SAT}$$\mathsf{PP}$$k \geq 3$$\mathsf{MAJORITY}$ $\mathsf{kSAT}$$\mathsf{PP}$

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

Prawdą jest, że redukcja Cooka-Levina jest oszczędna i wytwarza 3CNF z danego CNF. Ponieważ jest -kompletny, natychmiast wynika z tego, że jest również -kompletny przy ograniczonych oszczędnościach. Jednak, jak już wspomniano w komentarzu, oszczędne redukcje nie zachowują większości. Redukcje te wprowadzają zmienne pomocnicze w celu zmniejszenia wielkości klauzul, ale z kolei te zmienne pomocnicze zwiększają całkowitą liczbę przypisań. Rozważmy na przykład 4CNF, który składa się z jednej klauzuli:# P # 3 C N F # $\mathsf{\#CNF}$$\mathsf{\#P}$$\mathsf{\#3CNF}$$\mathsf{\#P}$

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

który przekształca się w

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

za pomocą zmiennej pomocniczej i wreszcie do 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).$

Ta transformacja wyraźnie zachowuje liczbę modeli, ale łatwo zauważyć, że większość nie jest zachowana. ma 15 spełniających zadania z 16 zadań, podczas gdy ψ ma 15 spełniających zadania z 32 zadań. W pierwszym przypadku większość spełnia, natomiast w drugim przypadku większość nie spełnia.$\phi$$\psi$

Dlatego też nie, dowód, że # 3CNF jest -Complete może być dostosowany, aby udowodnić, że M J 3 C N C to P P -Complete? Pozostaje otwarte, czy M A J 3 C N F jest problemem kompletnym P P przy wielu redukcjach jeden.$\mathsf{\#P}$$\mathsf{MAJ3CNF}$$\mathsf{PP}$$\mathsf{MAJ3CNF}$$\mathsf{PP}$

nie daje wiele wgląd pomiędzy różnicami # P i P P . W rzeczywistości wariant decyzji decyzyjnej nr 3 C N F , powiedzmy D # 3 C N F , jest zdefiniowany następująco: biorąc pod uwagę CNF ϕ i liczbę m ≥ 0 , zdecyduj, czy ϕ ma co najmniej m spełniających przypisań. Uwaga: dla D # 3 C N $\mathsf{MAJ3CNF}$$\mathsf{\#P}$$\mathsf{PP}$$\mathsf{\#3CNF}$$\mathsf{D\#3CNF}$$\phi$$m \geq 0$$\phi$$m$$\mathsf{D\#3CNF}$, nie dbamy o większość. W ten sposób możemy przekształcić dowolny CNF w 3CNF, stosując redukcję oszczędną, co dowodzi, że jest P P- skompletowany przy wielu redukcjach jeden. M J 3 C N C to po prostu inny problem niż D # 3 C N F .$\mathsf{D\#3CNF}$$\mathsf{PP}$$\mathsf{MAJ3CNF}$$\mathsf{D\#3CNF}$