Um caso fácil de SAT que não é fácil para a resolução em árvore

10

Existe uma classe natural de fórmulas de CNF - de preferência uma que tenha sido previamente estudada na literatura - com as seguintes propriedades:C

  • é um caso fácil de SAT, como, por exemplo, Horn ou 2-CNF, ou seja, a associação empode ser testada em tempo polinomial e as fórmulaspodem ser testadas quanto à satisfação em tempo polinomial.CF CCFC
  • As fórmulas insatisfatórias não são conhecidas por terem refutações de resolução curtas (tamanho polinomial) em árvore. Ainda melhor seria: existem fórmulas insatisfatórias em para as quais é conhecido um limite inferior super-polinomial para resolução semelhante a uma árvore.CFCC
  • Por outro lado, as fórmulas insatisfatórias em são conhecidas por terem provas curtas em algum sistema de prova mais forte, por exemplo, em resolução semelhante a dag ou em algum sistema ainda mais forte.C

n n NC não deve ser muito esparso, ou seja, conter muitas fórmulas com variáveis, para todos (ou pelo menos para a maioria dos valores de) . Também deve ser não trivial, no sentido de conter fórmulas satisfatórias e também insatisfatórias.nnN

A abordagem a seguir para resolver uma fórmula arbitrária CNF deve ser significativa: encontre uma atribuição parcial na fórmula residual em e aplique o algoritmo de tempo polinomial para fórmulas em a . Portanto, eu gostaria de outras respostas além das restrições totalmente diferentes da resposta atualmente aceita, pois acho raro que uma fórmula arbitrária se torne uma restrição totalmente diferente após a aplicação de uma restrição.α F α C C F αFαFαCCFα

Jan Johannsen
fonte
11
Jan, acho que ainda é possível dar exemplos artificiais, por exemplo, a união do PHP Horn. Não sei como se pode excluir formalmente esses exemplos. Você quer alguma aula que tenha um nome e que tenha sido estudada? : (ps se você explicar por que você está olhando para a classe tal que possa ajudar com o que requisitos adicionais a classe deve satisfazer.)
Kaveh
não tenho certeza sobre a última frase. problemas de pombo podem ter fórmulas verdadeiras e falsas, certo? geralmente são apenas as fórmulas verdadeiras, não sei onde estão as fórmulas falsas em um artigo, alguém mais viu isso? uma fórmula natural de pomba falsa seria aquela que tentasse atribuir pombos a n buracos. n+1n
vzn
@ Kaveh, você está certo, mas provavelmente nunca se pode descartar exemplos artificiais. Eu tentei esclarecer um pouco a questão.
Jan Johannsen
A condição desejada em sua última edição requer essencialmente uma classe hereditária. Observe que a codificação direta de todos os diferentes produz uma classe hereditária de instâncias SAT. Talvez você possa esclarecer por que o exemplo principal que temos (como sugerido por três comentários / respostas) não é adequado?
András Salamon
11
Acho que o que Jan quer é uma classe natural de fórmulas, não uma família de fórmulas. A dificuldade é "natural" e "classe", são conceitos informais. Eu acho que uma condição que se pode colocar para ser uma classe é exigir algum nível de expressividade ou fechamento, para que famílias de fórmulas como PHP não sejam contadas como classe. E quanto à naturalidade, acho que se a classe foi estudada anteriormente ou tem um nome, é provável que seja natural.
precisa

Respostas:

10

Parece que você está interessado em diferentes restrições (e sua última frase está no caminho certo). Essas são instâncias não triviais do princípio do buraco de pombo, em que o número de pombos não é necessariamente maior que o número de buracos e, além disso, alguns pombos podem ser barrados em alguns dos buracos.

Restrições diferentes podem ser decididas combinando em tempo polinomial de ordem baixa.

Quando restrições diferentes são expressas (usando uma das várias codificações) como instâncias SAT, o aprendizado de cláusulas orientadas a conflitos geralmente encontra rapidamente uma solução, se existir. No entanto, a resolução pura para o PHP precisa criar um conjunto de cláusulas superpolinomialmente grandes para mostrar que a instância é insatisfatória. Esse limite claramente se aplica a esse problema mais geral. Por outro lado, lembre-se de que a codificação do PHP por Cook permite a extensão estendida de tamanho polinomial refutações de resolução .

  • SA Cook, Uma pequena prova do princípio do buraco de pombo usando resolução estendida , Notícias SIGACT 8 28–32, 1976. doi: 10.1145 / 1008335.1008338

Um trabalho recente nesse sentido é o Capítulo 5 de tese Sergi Oliva , que formou a base de um trabalho com Alberto Atserias no CCC 2013.

Espero que você esteja ciente do resultado clássico de Cook, então talvez você pretenda restringir o poder do sistema de provas em sua terceira condição?

András Salamon
fonte
Jan não tem certeza se é isso que Jan está procurando, pois pede especificamente a CNF.
26613 Mikolas
@ Mikolas: você poderia esclarecer com o que está preocupado?
András Salamon
11
Eu quis dizer que, se tenho algum resultado sobre restrições diferentes, não está claro como esse resultado se traduz em CNF. Pelo que entendi as perguntas, Jan queria que as CNFs fossem difíceis para res-tree, mas fáceis para outra coisa (por exemplo, dag-res). Também não está claro para mim por que o PHP seria um exemplo disso, porque o PHP também é exponencial para os dag-res. (BTW a tese referenciada parece puro!)
Mikolas
@mikolas como eu entendo a pergunta, se instâncias satisfatórias / insatisfatórias da família podem ser reconhecidas no tempo P, mas é difícil para a resolução de árvores ou DAG, é isso que se procura. agora não tenho certeza de que isso seja apontado em qualquer documento, mas, a qualquer momento (alguém sabe mais?), as instâncias PHP sat / unsat podem ser reconhecidas em tempo P.
vzn
1

Não sei por que alguém exigiria também fórmulas sat, mas existem alguns artigos sobre a separação entre a resolução Geral e a Árvore, por exemplo [1]. Parece-me que é isso que você quer.

[1] Ben-Sasson, Eli, Russell Impagliazzo e Avi Wigderson. "Perto da separação ideal entre resolução de árvore e resolução geral". Combinatorica 24.4 (2004): 585-603.

Mikolas
fonte
11
Estou bem ciente dessas separações entre a resolução de árvore e a de dag, mas isso fornece apenas uma família de fórmulas. Este é precisamente o tipo de exemplo artificial que eu estava tentando evitar.
Jan Johannsen
0

Você pode estar interessado em fórmulas SAT com pequena "largura de banda" (logarítmica) ou "largura de árvore". Essas fórmulas são particionáveis ​​recursivamente de tal maneira que o limite de comunicação entre partições é pequeno e, portanto, uma abordagem de programação dinâmica enumerativa pode ser usada para resolvê-las. O tópico foi popular nos anos noventa. Certa vez, contei exatamente o número de ciclos hamiltonianos em um pequeno gráfico de largura de árvore de 24.000 vértices; portanto, os problemas de # P com pequena largura de árvore também são solucionáveis. Bodlaender é uma referência importante.

daniel pehoushek
fonte
Penso que pelo menos as fórmulas de largura constante da árvore têm refutações curtas de resolução semelhante à árvore. Portanto, não acho que essa classe atenda aos requisitos da pergunta.
Jan Johannsen
-1

este artigo a seguir parece próximo ao que é solicitado de algumas maneiras (se não se encaixar, talvez JJ possa esclarecer o porquê). a pergunta quer descartar instâncias PHP (pigeonhole) com base na falta de fórmulas verdadeiras / falsas, mas (conforme citado nas outras respostas) PHP é um dos geradores de casos / instâncias mais bem estudados do lado da teoria e tem sempre foi um gerador de fórmulas satisfatórias / insatisfatórias, embora as fórmulas satisfatórias sejam menos enfatizadas / estudadas.

nmmnm>nmn

outra abordagem seria seguir um ângulo mais empírico e apenas gerar instâncias aleatórias (presumivelmente em torno do ponto de transição satisfatório fácil-difícil-fácil 50%) e filtrá-las para atender aos critérios estabelecidos. seria necessário implementar implementações de resolução em árvore / resolução DAG ou "sistemas mais fortes".

vzn
fonte
11
O mesmo comentário da resposta de @Mikolas 'se aplica aqui.
Jan Johannsen
11
Não entendi o seu comentário, preciso de mais informações. estou seguindo o comentário de mikolas "Como eu entendo as perguntas, Jan queria que as CNFs fossem difíceis para res-tree, mas fáceis para outra coisa (por exemplo, dag-res)." o que você quer dizer com "isso dá apenas uma família de fórmulas"? sua pergunta está pedindo uma família de fórmulas.
vzn
11
Não, minha pergunta está pedindo uma classe de fórmulas. A diferença para mim é que essas famílias de fórmulas têm no máximo uma fórmula por número de variáveis, enquanto uma classe apropriada deve ter muitas fórmulas para cada número de variáveis, entre aquelas satisfatórias e insatisfatórias.
Jan Johannsen
Eu já expliquei em vários lugares (cf. o comentário aqui e em outras respostas e sobre a pergunta) por que não é isso que estou procurando !! Em particular, leia o último parágrafo da pergunta!
Jan Johannsen