Rendre les solveurs SAT compétitifs avec des algorithmes spécialisés

11

Quels sont les obstacles à la compétitivité des solveurs SAT avec des algorithmes de graphes spécialisés? En d'autres termes, est-il possible de s'attendre à des solveurs SAT qui peuvent remplacer le rôle de concepteur d'algorithmes - c'est-à-dire être capables de reconnaître automatiquement la structure du problème et de la résoudre aussi rapidement qu'un algorithme spécialisé?

Voici quelques exemples qui me semblent difficiles pour les solveurs SAT d'aujourd'hui:

  • Compter des ensembles indépendants de taille . Le codage "x est un ensemble indépendant de taille k" donne une grande formule difficile à résoudre. Un solveur SAT idéal reconnaîtrait que ce problème est facile sur un graphique de largeur d'arbre borné avec l'ajout d'une variable "count" supplémentaire pour les sacs.k

  • Trouver l'arbre minimum de Steiner. Encore une fois, "Steiner tree" a une contrainte globale, cependant, un algorithme spécialisé (comme ici ) facilite la tâche en ajoutant une variable supplémentaire

  • Tout problème qui se réduit à des correspondances parfaites planes.

ds.algorithms graph-theory sat Yaroslav Bulatov
la source
cela ne se produit-il pas déjà? C'est une astuce populaire pour réduire un problème en SAT, puis exécuter un solveur.
Suresh Venkat
Oui, mais sont-ils compétitifs? Je me demande s'il existe un solveur SAT qui pourrait prendre un simple ensemble de contraintes décrivant le sous-graphe eulérien d'un graphe planaire et faire #SAT en temps polynomial
Yaroslav Bulatov

Réponses:

7

Il y a un beau papier qui aide à visualiser la structure interne des instances SAT. Voir Visualisation des instances SAT et des exécutions de l'algorithme DPLL par Carsten Sienz (apparu dans SAT 2004). Fondamentalement, il dessine un graphe que l'auteur appelle "graphe d'interaction variable" (selon certaines règles) pour visualiser la relation entre les clauses satisfaites. L'auteur le montre par plusieurs exécutions partielles de DPLL.

La revendication principale est que ces techniques de visualisation pourraient être utilisées pour détecter la structure et concevoir un algorithme approprié pour celle-ci. Cependant, on ne sait toujours pas comment détecter efficacement des structures comme celle présentée dans l'article. Il est bien connu que les algorithmes SAT pour un problème spécifique se comportent mal dans d'autres problèmes. Il n'y a donc pas de "déjeuner gratuit", bien que cette affirmation ne puisse pas être formellement formulée à ma connaissance.

Marcos Villagra
la source
Je pense que le théorème pertinent "pas de déjeuner gratuit" est le "pas de déjeuner gratuit pour la recherche" no-free-lunch.org . Fondamentalement, nous ne pouvons pas nous permettre de rechercher toutes les structures à problème possibles et devons orienter notre recherche vers des structures particulières. Je pense que c'est OK puisque les concepteurs d'algorithmes humains le font déjà
Yaroslav Bulatov