Status de preenchimento de PP de MAJ3SAT

10

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?

Fabio Cozman
fonte
4
A redução típica do CircuitSAT para o 3sat não funciona porque introduz muitas novas variáveis. Portanto, enquanto você pode ter 2 ^ (n-1) +1 atribuindo satisfações a um determinado circuito com n entradas, e você terá muitos para a instância 3sat, o número de vars na instância 3cnf é muito maior que n, para que esse número não seja mais "a maioria das tarefas satisfatórias". Observe que o Maj-3sat ainda é pelo menos NP difícil, porque você pode adicionar muitas atribuições fictícias de satisfação.
Ryan Williams
@RyanWilliams Que tal pegarmos essa instância 3CNF, negá-la e obter uma instância 3DNF (a negação leva tempo poli e quando você nega uma expressão CNF, obtém uma expressão DNF). Então a instância CNF original tinha mais de (2 ^ (n-1)) satisfazendo atribuições de verdade se e somente se a instância 3DNF tiver mais de (2 ^ ((n + K) -1) satisfazendo atribuições de verdade, onde K é o número de variáveis ​​adicionais ...
Tayfun Pay
A conversão de cnf em dnf não leva polytime em geral. Verificação rápida de sanidade: se tiver, P = NP ... verificação mais complexa: existem cnfs de cláusulas poli (n) cujos dnfs equivalentes mínimos têm muitas cláusulas. Veja, por exemplo, scholar.google.com/…
Ryan Williams
@RyanWilliams 1) Leva um tempo poli para negar uma expressão booleana 2) Quando você nega um CNF, obtém um DNF e vice-versa. Mais importante ainda, negar um CNF no tempo polinomial e obter um DNF em troca não altera a complexidade desse problema. Você precisaria encontrar uma atribuição de verdade falsificada para a fórmula CNF negada, que agora é uma fórmula DNF. É NP-Complete encontrar uma atribuição de verdade falsificada para uma fórmula DNF ...
Tayfun Pay
@RyanWilliams Conheço os trabalhos que você citou .. No entanto, você obtém uma expressão DNF quando nega uma expressão CNF. E isso leva tempo polinomial em relação ao comprimento da entrada.
Tayfun Pay

Respostas:

1


MAJ3CNFPP



PP

MAJORITY SATPPk3MAJORITY kSATPP

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

#CNF#P#3CNF#P

ϕ=(x1x2x3x4)

que é transformado em

ϕ=(x1x2y)(y(x3x4))

y

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

ϕψ

#PMAJ3CNFPPMAJ3CNFPP

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

Heyheyhey
fonte
3SATP3SAT