dc.contributor.author
Ansótegui Gil, Carlos José
dc.contributor.author
Bonet, Maria Luisa
dc.contributor.author
Giráldez-Cru, Jesús
dc.contributor.author
Levy, Jordi
dc.date.accessioned
2024-12-05T21:44:48Z
dc.date.available
2024-12-05T21:44:48Z
dc.date.issued
2018-11-09T09:49:33Z
dc.date.issued
2018-11-09T09:49:33Z
dc.identifier
https://doi.org/10.1007/978-3-319-08587-6_8
dc.identifier
http://hdl.handle.net/10459.1/65063
dc.identifier.uri
http://hdl.handle.net/10459.1/65063
dc.description.abstract
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.
dc.description.abstract
This research has been partially founded by the MINECO research project TASSAT (TIN2010-20967).
dc.publisher
Springer Verlag
dc.relation
info:eu-repo/grantAgreement/MICINN//TIN2010-20967-C04-01/ES/TASSAT: TEORIA, APLICACIONES Y SINERGIA EN SAT, CSP Y FDL/
dc.relation
info:eu-repo/grantAgreement/MICINN//TIN2010-20967-C04-03/ES/TEORIA, APLICACIONES Y SINERGIA EN SAT, CSP Y FDL/
dc.relation
info:eu-repo/grantAgreement/MICINN//TIN2010-20967-C04-04/ES/TEORIA, APLICACIONES Y SINERGIA EN SAT, CSP Y FDL/
dc.relation
Versió postprint del document publicat a https://doi.org/10.1007/978-3-319-08587-6_8
dc.relation
Lecture Notes in Computer Science, 2014, vol. 8562, p. 107-121
dc.rights
(c) Springer Verlag, 2014
dc.rights
info:eu-repo/semantics/openAccess
dc.subject
Fractal dimension
dc.title
The Fractal Dimension of SAT Formulas
dc.type
info:eu-repo/semantics/article
dc.type
info:eu-repo/semantics/acceptedVersion
