1-em-3 exclusivo sentado

Question

Suponha que eu tenha uma fórmula CNF com cláusulas de tamanho 2 e 3. Tem uma tarefa satisfatória única.

Eu conheço o valor de cada bit da tarefa exclusiva porque foi feita a partir de um circuito de multiplicação binária onde eu multipliquei dois primes números A e B de tal forma que um * b= s onde é um número semibrime. Eu adicionei as condições que um!= 1, b!= 1 e um <= b, então adicionado o valor de s à fórmula Certifique-se de que a atribuição seja única. A única maneira de satisfazer a fórmula é colocar os valores de A e B em ordem correta nos bits de entrada.

O número de verdadeiros literais em cada cláusula é 1, 2 ou 3. Porque eu conheço o valor de cada bit, posso dizer exatamente quais literais são verdadeiros em cada cláusula e contam-os. Por exemplo, eu sei quais cláusulas são satisfeitas por exatamente 1 literal. E esse literal é logicamente parte da solução única.

Minha pergunta é simples: se eu remover todas as cláusulas com mais de 1 verdadeiro literal, a tarefa necessariamente ainda será única?

Em outras palavras, se eu quisesse anotar uma prova de resolução (provavelmente exponencialmente longa) para demonstrar que a solução é única (outro problema de solução, em CO-NP), posso anotá-lo usando apenas as cláusulas com 1 verdadeiro literal?

Intuitivamente, acho que sim, mas não consigo defender meu ponto de vista, mesmo quando pensar no equivalente do 2,sat.

Answer 1

Considere o seguinte CNF: $$ (um \ lor \ lnot b) \ terra (\ lnot a \ lor b) \ terra (a \ lor b). $$ Ele tem uma tarefa satisfatória única, $ a= b=top $ , que satisfaz a última cláusula duas vezes.No entanto, se você remover a última cláusula, você obterá outra tarefa satisfatória, $ a= b=bot $ .