TitleLocality in Random SAT Instances
Publication TypeConference Paper
Year of Publication2017
AuthorsGiráldez-Cru J, Levy J
Conference NameProceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017
Conference LocationMelbourne, Australia
ISBN Number978-0-9992411-0-3

Despite the success of CDCL SAT solvers solving industrial problems, there are still many open questions to explain such success. In this context, the generation of random SAT instances having computational properties more similar to real-world problems becomes crucial. Such generators are possibly the best tool to analyze families of instances and solvers behaviors on them.

In this paper, we present a random SAT instances generator based on the notion of locality. We show that this is a decisive dimension of attractiveness among the variables of a formula, and how CDCL SAT solvers take advantage of it. To the best of our knowledge, this is the first random SAT model that generates both scale-free structure and community structure at once.