The Fractal Dimension of SAT Formulas

Ansótegui Gil, Carlos José; Bonet, Maria Luisa; Giráldez-Cru, Jesús; Levy, Jordi

doi:https://doi.org/10.1007/978-3-319-08587-6_8

Visualitza/Obre

Postprint (789.3Kb)

Data de publicació

2014

Autor/a

Ansótegui Gil, Carlos José

Bonet, Maria Luisa

Giráldez-Cru, Jesús

Levy, Jordi

Citació recomanada

Ansótegui Gil, Carlos José; Bonet, Maria Luisa; Giráldez-Cru, Jesús; Levy, Jordi; . (2014) . The Fractal Dimension of SAT Formulas. Lecture Notes in Computer Science, 2014, vol. 8562, p. 107-121. https://doi.org/10.1007/978-3-319-08587-6_8.

Resum

Modern SAT solvers have experienced a remarkable progress on solving industrial instances. Most of the techniques have been developed after an intensive experimental process. It is believed that these techniques exploit the underlying structure of industrial instances. However, there is not a precise

definition of the notion of structure. Recently, there have been some attempts to analyze this structure in terms of complex networks, with the long-term aim of explaining the success of SAT solving techniques, and possibly improving them. We study the fractal dimension of SAT instances with the aim of complementing the model that describes the structure of industrial instances. We show that many industrial families of formulas are self-similar, with a small fractal dimension. We also show how this dimension is affected by the addition of learnt clauses during the execution of SAT solvers.

URI

http://hdl.handle.net/10459.1/65063

DOI

https://doi.org/10.1007/978-3-319-08587-6_8

És part de

Lecture Notes in Computer Science, 2014, vol. 8562, p. 107-121