Quais são os obstáculos para tornar competitivos os solucionadores SAT com algoritmos gráficos especializados? Em outras palavras, é possível esperar solucionadores SAT que possam substituir o papel de projetista de algoritmos - ou seja, ser capaz de reconhecer automaticamente a estrutura do problema e resolvê-la tão rapidamente quanto um algoritmo especializado?
Aqui estão alguns exemplos que acho desafiadores para os solucionadores de SAT de hoje:
Contando conjuntos independentes de tamanho . A codificação "x é um conjunto independente de tamanho k" fornece uma fórmula grande que é difícil de resolver. Um solucionador SAT ideal reconheceria que esse problema é fácil no gráfico de largura de árvore delimitada, com a adição de uma variável extra de "contagem" para sacos.
Encontrando uma árvore Steiner mínima. Novamente, a "árvore Steiner" tem uma restrição global; no entanto, um algoritmo especializado (como aqui ) facilita a tarefa adicionando uma variável extra
Qualquer problema que se reduz a combinações perfeitas planares.
fonte
Respostas:
Há um bom artigo que ajuda a visualizar a estrutura interna das instâncias do SAT. Consulte Visualizando instâncias SAT e execuções do algoritmo DPLL de Carsten Sienz (publicado em SAT 2004). Basicamente, ele desenha um gráfico que o autor chama de "gráfico de interação variável" (de acordo com algumas regras) para visualizar a relação entre as cláusulas satisfeitas. O autor mostra isso por várias execuções parciais do DPLL.
A principal alegação é que essas técnicas de visualização podem ser usadas para detectar a estrutura e projetar um algoritmo apropriado para ela. No entanto, ainda não está claro como podemos detectar eficientemente estruturas como a apresentada no artigo. É sabido que os algoritmos SAT para um problema específico se comportam mal em outros problemas. Portanto, existe um "almoço grátis", embora essa afirmação não possa ser formalmente declarada, até onde eu saiba.
fonte