Soluções de contagem de fórmulas Monotone-2CNF

13

Uma fórmula Monotone-2CNF é uma fórmula CNF em que cada cláusula é composta por exatamente 2 literais positivos.

Agora, eu tenho uma fórmula Monotone-2CNF . Seja o conjunto de atribuições satisfatórias deEu também tenho um oracle que é capaz de fornecer as seguintes informações:FSFO

  1. A cardinalidade do conjunto (ou seja, o número de soluções de ).SF
  2. Dada uma variável : x
    • O número de soluções em contendo o literal positivo .Sx
    • O número de soluções em contendo o literal negativo .S¬x
  3. Dadas 2 variáveis e : x1x2
    • O número de soluções em contendo .Sx1x2
    • O número de soluções em contendoSx1¬x2 .
    • O número de soluções em S contendo ¬x1x2 .
    • O número de soluções em S contendo ¬x1¬x2 .

Note-se que o oráculo é "limitada": ele funciona somente em F , não pode ser usado em uma fórmula F 'F .OFFF


Questão:

Dadas as 3 variáveis , x 2 , x 3, é possível determinar o número de soluções em S contendo ¬ x 1¬ x 2¬ x 3 em tempo polinomial, utilizando F e a informação fornecida por S ?x1x2x3S¬x1¬x2¬x3FO

Nota:

Você pode substituir na questão com qualquer outra coisa que um dos 8 possíveis combinações de x 1 , x 2 , x 3 . O problema continuaria o mesmo.¬x1¬x2¬x3x1x2x3


Fato empírico:

Me deparei com o seguinte fato empírico há uma semana. Deixe ser o conjunto das soluções contendo ¬ x 1¬ x 2 , e deixar S ¬ x 1¬ x 2x 3S ser o conjunto das soluções contendo ¬ x 1¬ x 2x 3 . Agora, parece ser que, se a condição CS¬x1¬x2S¬x1¬x2S¬x1¬x2x3S¬x1¬x2x3Cmantém, esse relacionamento também mantém:

ondeφ=1.618033 ...é a proporção áurea. A condiçãoCparece ser a seguinte:"x1,x2,x3são mencionados emFquase o mesmo número de vezes".|S¬x1¬x2||S¬x1¬x2x3|ϕ

ϕ=1.618033...Cx1x2x3F

Giorgio Camerani
fonte
1
Quando você diz "soluções contendo o literal negativo -x" - você quer dizer "soluções com x = 0"?
Noam
@ Noam: Sim, exatamente.
Giorgio Camerani 11/11/10
1
Observação fácil: como o número de perguntas possíveis para o oráculo O é polinomialmente limitado, sem perda de generalidade, você pode consultar todas as perguntas no início de um algoritmo. Portanto, podemos substituir o oráculo por informações adicionais, com a promessa de que esses números estão corretos. Eu acho que essa formulação de promessa é um pouco mais simples do que considerá-la um oráculo.
Tsuyoshi Ito
@ Tsuyoshi: Sim, eu concordo com você.
Giorgio Camerani
1
@vzn: A versão decisão do 2CNF está em . Esta é a versão de contagem do caso monótono (dada a fórmula F monofônica 2CNF F , é necessário calcular quantas atribuições satisfatórias ele possui). PF
Giorgio camerani

Respostas:

5

Para usar esse fato empírico, você realmente deseja saber se os números aproximados podem dar aos outros números aproximados. Mas, no caso exato, acho que pode haver uma maneira direta de mostrar que isso é difícil. Aqui está um esboço.

Primeira nota que tarefas satisfatórias correspondem a conjuntos independentes em um gráfico. Vou usar a frase "S-projecções de I (L)" para descrever o mapeamento de função para o número de conjuntos independentes I com I S = T . As "projeções k" são as projeções S para todos os subconjuntos S de V com | S | = k .TSIS=T|S|=k

Esboço da prova:

  1. Se 2 projeções fornecerem 3 projeções, elas também fornecerão projeções k em polytime para cada k.
  2. Se 2 projeções fornecem 4 projeções, então o número de conjuntos independentes de um gráfico está em FP, então FP = # P.

(1) Seja tal que as projeções (k-1) produzam projeções k. Dado um gráfico, seus k-projecções, e x 1 , . . . , X k , v L , iremos calcular as projecções no x 1 , . . . , x k , v .k3x1,...,xk,vGx1,...,xk,v

Defina o gráfico anexando um vértice novo a v. Isso pode ser visto como ponderação v. As projeções (k-1) de G ' podem ser calculadas porque conhecemos as projeções k de G. Então, temos o projeções k de G . E isso dá x 1 , . . . , x k , v - projeções de G.GGGx1,...,xk,v

(2) Dado um gráfico, ordenar as bordas e definir L k ter bordas um e 1 , . . . , e k . As 2 projeções de G k + 1 podem ser calculadas a partir das 4 projeções de G k . O número de conjuntos independentes em G 0 é 2 | G | . Iterativamente, as 4 projeções de G podem ser calculadas em tempo polinomial.e1,...,emGke1,...,ekGk+1GkG02|G|

Colin McQuillan
fonte
Eu preferiria não usar esse fato empírico! Eu prefiro a contagem exata, é claro. Mas, aliás, notei esse fato ao tentar determinar a contagem exata.
Giorgio Camerani
Obrigado pela sua resposta. Sim, é difícil: como você diz, uma resposta positiva a essa pergunta implicaria #P = FP.
Giorgio camerani
7

Algumas observações, não uma resposta.

Além da nota à pergunta, qualquer combinação de 3 literais pode ser expressa em termos de qualquer outra combinação de literais nas mesmas variáveis, juntamente com um pequeno número de termos que o oráculo pode fornecer. Isso se segue observando o diagrama de Venn de 3 conjuntos que se cruzam e expressando cada uma das 8 regiões em termos das outras regiões. Observe que isso não requer que a fórmula seja monótona ou 2CNF.

Também está claro que o número de soluções que satisfazem qualquer conjunto 3-literal pode ser expresso como a soma de termos, cada um dos quais é 0 ou 1, expressando uma atribuição específica a todas as variáveis. Cada um deles pode ser avaliado em tempo linear, mas existem muitos termos a serem avaliados exponencialmente, portanto, isso não atende aos requisitos.2n3

Portanto, a questão é realmente se é possível explorar a propriedade de ser 2CNF monótono para compactar essa expressão de tamanho exponencial em tamanho polinomial.

Tentei analisar uma pergunta mais simples, restringindo o oráculo a apenas uma sequência de conselhos com o número de soluções, quando as contagens para combinações literais simples ou aos pares não estão disponíveis. Não vejo nenhuma maneira de explorar o conhecimento do número de soluções para obter um cálculo rápido do número de soluções em relação a qualquer literal único.

Sx1|S|

András Salamon
fonte
2
De fato, as informações fornecidas precisam ser poderosas o suficiente para derrotar a dureza subjacente. Sabe-se que não há fpras para soluções monotônicas de 2-SAT, a menos que NP = RP.
Mhum 12/10/10
DDFD
@ Walter: Sim, eu entendo isso. Meu argumento é que mesmo um caso muito mais simples não está claro: passando do número total de soluções para o número de soluções contendo um único literal.
András Salamon
1
Pode ser que sua fórmula seja essencialmente linear: conjuntos independentes em um caminho seguem a sequência de Fibonacci. Uma maneira de ver isso é que a função de partição (1 1; 1 0) tem phi como um valor próprio.
Colin McQuillan
3
Aconteceu de eu encontrar alguns slides discutir um resultado mais rigoroso: isid.ac.in/~antar/Talks/Counting-Hard-Core_KBS_slides.pdf (ver página 11)
Colin McQuillan