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:
- A cardinalidade do conjunto (ou seja, o número de soluções de ).
-
Dada uma variável :
- O número de soluções em contendo o literal positivo .
- O número de soluções em contendo o literal negativo .
-
Dadas 2 variáveis e :
- O número de soluções em contendo .
- O número de soluções em contendo .
- O número de soluções em contendo .
- O número de soluções em contendo .
Note-se que o oráculo é "limitada": ele funciona somente em F , não pode ser usado em uma fórmula F ' ≠ F .
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 ?
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.
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 2 ∧ x 3 ⊂ S ser o conjunto das soluções contendo ¬ x 1 ∧ ¬ x 2 ∧ x 3 . Agora, parece ser que, se a condição Cmanté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".
fonte
Respostas:
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 .T⊂S I∩S=T |S|=k
Esboço da prova:
(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 .k≥3 x1,...,xk,v∈G x1,...,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.G′ G′ G′ x1,...,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,...,em Gk e1,...,ek Gk+1 Gk G0 2|G|
fonte
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.2n−3
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.
fonte