Pasar al contenido principal

TEORIA, APLICACIONES Y SINERGIA EN SAT, CSP Y FDL

TIN2010-20967-C04-04

•
Nombre agencia financiadora Ministerio de Ciencia e Innovación
Acrónimo agencia financiadora MICINN
Programa Programa Nacional de Proyectos de Investigación Fundamental
Subprograma Subprograma de Proyectos de Investigación Fundamental no Orientada
Convocatoria Proyectos I+D
Año convocatoria 2010
Plan Estatal 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Unidad de gestión Subdirección General de Proyectos de Investigación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA
Identificador persistente http://dx.doi.org/10.13039/501100004837

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

The Fractal Dimension of SAT Formulas

  • Ansótegui Gil, Carlos José
  • Bonet, Maria Luisa
  • Giráldez-Cru, Jesús
  • Levy, Jordi
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., This research has been partially founded by the MINECO research project TASSAT (TIN2010-20967).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The Fractal Dimension of SAT Formulas

  • Ansótegui Gil, Carlos José
  • Bonet, Maria Luisa
  • Giráldez-Cru, Jesús
  • Levy, Jordi
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., This research has been partially founded by the MINECO research project TASSAT (TIN2010-20967).