La mesure de la difficulté des instances SAT

Question

Étant donné une instance de SAT, je voudrais être en mesure d'estimer combien il sera difficile de résoudre l'instance.

La première consiste à exécuter solveurs existants, mais ce genre de défaites le but d'estimer la difficulté. Une autre façon peut-être à la recherche d'un rapport des clauses aux variables, comme cela se fait pour les transitions de phase dans-SAT aléatoire, mais je suis sûr que des méthodes existent mieux.

Étant donné une instance de SAT, sont là quelques heuristiques rapides pour mesurer la difficulté? La seule condition est que ces heuristiques être plus rapide que fait courir les solveurs SAT existantes sur l'instance.

---

question connexe

Quels problèmes SAT sont faciles sur cstheory.SE. Cette question pose des questions sur les ensembles de cas traitables. Ceci est une question similaire, mais pas exactement la même chose. Je suis vraiment intéressé par une heuristique qui donne un seul exemple, fait une sorte de conjecture semi-intelligente si l'instance sera très difficile à résoudre.

Answer 1

Ceci est en général, une question de recherche très pertinent et intéressant. « Une façon est d'exécuter solveurs existants ... » et à quoi cela même nous dire exactement? On pouvait voir empiriquement qu'une instance semble difficile pour un solveur spécifique ou un algorithme spécifique / heuristique, mais qu'est-ce qu'il dire vraiment la dureté de l'instance?

Une façon qui a été poursuivi est l'identification des différentes propriétés structurelles des instances qui conduisent à des algorithmes efficaces. Ces propriétés sont en effet d'être ont préféré « facilement » identifiable. Un exemple est la topologie du graphe de contraintes sous-jacente, mesurée à l'aide de différents paramètres de largeur de graphique. Par exemple, il est connu qu'une instance est résoluble en temps polynomial si la largeur arborescente du graphe de contrainte sous-jacente est limitée par une constante.

Une autre approche a mis l'accent sur le rôle de structure cachée des instances. Un exemple est le ensemble porte dérobée , ce qui signifie l'ensemble des variables telles que lorsqu'ils sont instanciés, le problème restant à Simplifie une classe traitable. Par exemple, Williams et al., 2003 [1] montrent que même en tenant compte du coût de la recherche pour les variables de porte dérobée, on peut encore obtenir un avantage de calcul globale en mettant l'accent sur un ensemble de porte dérobée, à condition que l'ensemble est suffisamment faible. En outre, Dilkina et al., 2007 note [2] qu'un solveur appelé Satz-Rand est remarquablement bon à trouver de petites backdoors fortes sur une gamme de domaines expérimentaux.

Plus récemment, Ansotegui et al., 2008 [3] proposent l'utilisation de l'espace de la complexité arborescente comme mesure de solveurs-DPLL. Ils prouvent que l'espace aussi constant-borné implique l'existence d'un algorithme de décision en temps polynomial avec l'espace étant le degré du polynôme (théorème 6 dans le document). De plus, ils montrent l'espace est plus petit que la taille du vélo-liasses. En fait, dans certaines hypothèses, l'espace est plus petit que la taille des backdoors.

Ils formalisent aussi ce que je pense que vous êtes après, qui est:

  

Trouver une mesure $ \ psi $, et un algorithme qui donne une formule $ \ Gamma $ décide satisfiability dans le temps $ O (n ^ {\ psi (\ Gamma)}) $. Plus la mesure est, mieux il caractérise la dureté d'une formule .

---

[1] Williams, Ryan, Carla P. Gomes, et Bart Selman. « backdoors à la complexité des cas typiques. » Conférence internationale conjointe sur l'intelligence artificielle. Vol. 18, 2003.

[2] Dilkina, Bistra, Carla Gomes, et Ashish Sabharwal. « Compromis dans la complexité de Backdoor Détection. » Principes et pratique de la programmation par contraintes (CP 2007), pp. 256-270, 2007.

[3] Ansotegui, Carlos, Maria Luisa Bonet, Jordi Levy, et Felip Manya. « Mesure de la dureté des instances SAT. » Dans Actes de la Conférence nationale de 23 sur l'intelligence artificielle (de AAAI'08), pp. 222-228, 2008.

Answer 2

Puisque vous savez au sujet de la transition de phase, permettez-moi de mentionner quelques autres contrôles de simples que je suis au courant (qui sont probablement englobée par l'analyse graphique de contrainte):

• Certains des premiers générateurs SAT aléatoires par inadvertance créé des formules pour la plupart faciles parce qu'ils ont utilisé « densité constante », ce qui signifie une proportion à peu près égale de toutes les longueurs de clause. Ceux-ci étaient pour la plupart facile parce que 2-clauses et unités simplifient le problème de manière significative, comme on devrait s'y attendre, et des clauses très longues ne soit pas grand-chose de branchement ajouter ou facilitent encore plus hyper-résolution. Ainsi, il semble préférable de rester avec des clauses de longueur fixe et varient d'autres paramètres.
• De même, une puissante règle de simplification est l'élimination pure littérales. De toute évidence, une formule est vraiment seulement aussi dur que le nombre de littéraux impur qu'elle a. Étant donné que la résolution crée de nouvelles clauses de numérotation $ | x | * | \ lnot x | $ (ce qui signifie, le produit d'occurrences de $ x $ et sa négation), le nombre de fondants est maximisée quand il y a un nombre égal de littéraux positifs et négatifs pour chaque variable. Par conséquent, les générateurs SAT équilibré.
• Il y a aussi une technique appelée « No Triangle SAT », qui semble être assez frais [1], qui est une sorte de générateur dur instance qui interdit « triangles ». Un triangle est un ensemble de clauses contenant 3 variables $ v_1, v_2, V_3 $ qui se produisent par paires dans toutes les combinaisons dans un certain ensemble de clauses (par exemple, $ \ {v_1, v_2, ... \}, \ {v_2, V_3, ... \}, \ {v_1, V_3, ... \} $ ). , Les triangles ont apparemment tendance à faire une formule plus facile pour les solveurs connus.

[1] https://arxiv.org/pdf/1903.03592.pdf

Answer 3

En plus d'une excellente réponse de Juho, voici une autre approche:

Ercsey-Ravasz & Toroczkai, dureté d'optimisation comme le chaos transitoire dans une approche analogique à la satisfaction contrainte , le volume physique Nature 7, pages 966-970 (2011).

Cette approche consiste à réécrire le problème SAT dans un système dynamique, où tout attracteur de le système est une solution au problème SAT. Les bassins d'attraction du système sont plus fractale que le problème devient plus difficile, et donc la « difficulté » de l'instance SAT peuvent être mesurés en examinant comment chaotique les transitoires sont avant converge système.

En pratique, cela signifie à partir d'un groupe de solveurs de différentes positions initiales et portant sur le taux auquel solveurs échapper aux transitoires chaotiques avant qu'ils arrivent à un attracteur.

Il est pas difficile de trouver un système dynamique pour lequel les « solutions » sont des solutions à un problème donné SAT, mais il est un peu plus difficile à faire en sorte que les solutions sont tous attracteurs et non répulsifs. Leur solution est d'introduire des variables d'énergie (semblables à des multiplicateurs de Lagrange) pour représenter à quel point une contrainte est violée, et essayer d'obtenir le système pour minimiser l'énergie du système.

Il est intéressant, en utilisant leur système dynamique, vous pouvez résoudre les problèmes SAT en temps polynomiale sur un ordinateur analogique, ce qui en soi est un résultat remarquable. Il y a un hic; il peut exiger des tensions de façon exponentielle pour représenter les grandes variables d'énergie, vous pouvez donc malheureusement pas réaliser cela sur le matériel physique.