Estimating satisfiability

Yacine Boufkhad 1, 2 Thomas Hugel 2
1 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : The problem of estimating the proportion of satisfiable instances of a given CSP (constraint satisfaction problem) can be tackled through weighting. It consists in putting onto each solution a non-negative real value based on its neighborhood in a way that the total weight is at least 1 for each satisfiable instance. We define in this paper a general weighting scheme for the estimation of satisfiability of general CSPs. First we give some sufficient conditions for a weighting system to be correct. Then we show that this scheme allows for an improvement on the upper bound on the existence of non-trivial cores in 3-SAT obtained by Maneva and Sinclair (2008) [17] to 4.419. Another more common way of estimating satisfiability is ordering. This consists in putting a total order on the domain, which induces an orientation between neighboring solutions in a way that prevents circuits from appearing, and then counting only minimal elements. We compare ordering and weighting under various conditions.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2012, 160 (1-2), pp.19. 〈10.1016/j.dam.2011.10.005〉
Liste complète des métadonnées
Contributeur : Yacine Boufkhad <>
Soumis le : mardi 26 janvier 2016 - 14:55:06
Dernière modification le : vendredi 4 janvier 2019 - 17:33:21

Lien texte intégral




Yacine Boufkhad, Thomas Hugel. Estimating satisfiability. Discrete Applied Mathematics, Elsevier, 2012, 160 (1-2), pp.19. 〈10.1016/j.dam.2011.10.005〉. 〈hal-01262275〉



Consultations de la notice