Universitat de Lleida
    • English
    • català
    • español
  • English 
    • English
    • català
    • español
  • Login
Repositori Obert UdL
View Item 
  •   Home
  • Recerca
  • Informàtica i Enginyeria Industrial
  • Articles publicats (Informàtica i Enginyeria Industrial)
  • View Item
  •   Home
  • Recerca
  • Informàtica i Enginyeria Industrial
  • Articles publicats (Informàtica i Enginyeria Industrial)
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Generating hard SAT/CSP instances using expander graphs

Thumbnail
View/Open
Postprint (196.9Kb)
Issue date
2008
Author
Ansótegui Gil, Carlos José
Béjar Torres, Ramón
Fernàndez Camon, César
Mateu Piñol, Carles
Suggested citation
Ansótegui Gil, Carlos José; Béjar Torres, Ramón; Fernàndez Camon, César; Mateu Piñol, Carles; . (2008) . Generating hard SAT/CSP instances using expander graphs. Proceedings of the twenty-third National Conference on Artificial Intelligence, 2008, p. 1442-1443. http://hdl.handle.net/10459.1/46644.
Impact


Web of Science logo    citations in Web of Science

Scopus logo    citations in Scopus

Google Scholar logo  Google Scholar
Share
Export to Mendeley
Metadata
Show full item record
Abstract
In this paper we provide a new method to generate hard k-SAT instances. We incrementally construct a high girth bipartite incidence graph of the k-SAT instance. Having high girth assures high expansion for the graph, and high expansion implies high resolution width. We have extended this approach to generate hard n-ary CSP instances and we have also adapted this idea to increase the expansion of the system of linear equations used to generate XORSAT instances, being able to produce harder satisfiable instances than former generators.
URI
http://hdl.handle.net/10459.1/46644
Is part of
Proceedings of the twenty-third National Conference on Artificial Intelligence, 2008, p. 1442-1443
European research projects
Collections
  • Articles publicats (Informàtica i Enginyeria Industrial) [988]

Contact Us | Send Feedback | Legal Notice
© 2023 BiD. Universitat de Lleida
Metadata subjected to 
 

 

Browse

All of the repositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

Statistics

View Usage Statistics

D'interès

Política institucional d'accés obertDiposita les teves publicacionsDiposita dades de recercaSuport a la recerca

Contact Us | Send Feedback | Legal Notice
© 2023 BiD. Universitat de Lleida
Metadata subjected to