Qual a eficiência dos solucionadores de SAT baseados em DPLL em instâncias satisfatórias do PHP?

15

Sabemos que os solucionadores SAT baseados em DPLL falham em responder corretamente em instâncias insatisfatórias de (princípio do buraco de pombo), por exemplo, em "existe um mapeamento injetivo de n + 1 para n ":PHPn+1n

PHPnn+1:=(i[n+1] j[n] pi,j)(EuEu[n+1] j[n] (¬pEu,j¬pEu,j))

Estou procurando resultados sobre como eles se comportam em instâncias satisfatórias de , por exemplo, "existe um mapeamento injetivo de n para n ".PHPnn

Eles encontram uma tarefa satisfatória rapidamente nessas instâncias?

Kaveh
fonte
1
Por "falha em responder corretamente", você quer dizer "ficar sem recursos em valores suficientemente grandes de n"?
Vijay D
@Kaveh Você está permitindo a repetição de cláusulas e / ou repetição de variáveis ​​na mesma cláusula? Obrigado
Tayfun Pay
@VijayD, quero dizer que o algoritmo não retorna uma resposta correta em tempo polinomial para grande o suficiente . Espero que se possa demonstrar que um algoritmo baseado em DPLL funcionaria em tempo polinomial nessa família. n
Kaveh
@ Geekster, não tenho certeza do que você quer dizer. Eu tenho uma família particular de fórmulas. Você está perguntando se há repetição nessa fórmula?
Kaveh

Respostas:

14

Em casos satisfatível de , DPLL agentes de resolução SAT base fornecerá uma atribuição de satisfazer em tempo linear.PHP

Para entender o porquê, observe como a codificação CNF de uma instância insatisfatória de com n buracos e n + 1 pombos é sintaticamente idêntica a uma instância de k = n Graph Coloring, onde o gráfico de entrada é um clique de n + 1 vértices .PHPnn+1k=nn+1

Da mesma forma, o CNF que codifica de um exemplo de satisfatível com n furos e n pombos é sintactically idêntica a uma instância de k = n gráfico da coloração, onde o gráfico de entrada é um bando de n vértices.PHPnnk=nn

Agora, colorir uma clique de vértices com n cores é simples: digitalize os vértices e atribua a cada uma delas uma das cores restantes (as cores já atribuídas são automaticamente descartadas pela clique do gráfico, usando a propagação da unidade) . Qualquer que seja a cor que você escolher, ela será boa e o levará a uma tarefa satisfatória.nn

Do ponto de vista do solucionador de DPLL: sempre que tentar adivinhar o valor booleano de uma variável , esse valor estará correto (seja o que for), porque certamente haverá uma atribuição satisfatória na qual a variável v i terá o valor adivinhado. A propagação da unidade fará o resto do trabalho, guiando o solucionador ao longo do caminho satisfatório (em outras palavras: impedindo que ele adivinhe valores errados).vivi

A pesquisa então prossegue uma variável após a outra, linearmente, sempre que adivinhar corretamente.

Giorgio Camerani
fonte
Obrigado, é isso que eu estava esperando. A propósito, você conhece uma referência que afirma isso (por exemplo, "O algoritmo DPLL resolve as instâncias satisfatórias do PHP / GC em tempo linear")?
Kaveh
1
Você é bem vindo. Não conheço nenhuma referência que afirme isso, apenas a deduzi por algum raciocínio bruto. Não deve ser difícil provar isso formalmente, baseando-se no fato de que todo solucionador de SAT usa alguma heurística razoável, tanto na escolha da próxima variável quanto na adivinhação de seu valor booleano. Deve-se observar, de fato, que existe pelo menos uma heurística irracional que nos impede de chegar a uma solução em tempo linear (uma heurística irracional seria definir todas as variáveis ​​como falsas, até possível). Enquanto com uma heurística razoável, é garantido um tempo linear.
Giorgio Camerani
Concordo. Espero que alguém tenha declarado isso em algum lugar para que eu possa citar quando precisar. Gostaria de esperar mais alguns dias e, se ninguém der uma referência, aceitarei esta resposta. Obrigado novamente. :)
Kaveh
O prazer é meu ;-) Felicidades!
Giorgio Camerani