Change search
ReferencesLink to record
Permanent link

Direct link
Locality and hard SAT-instances
Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
2006 (English)In: Journal on Satisfiability, Boolean Modeling and Computation, Vol. 2Article in journal (Refereed) Published
Abstract [en]

In this note we construct a family of SAT-instance based on Eulerian graphs which are aimed at being hard for resolution based SAT-solvers. We discuss some experiments made with instances of this type and how a solver can try to avoid at least some of the pitfalls presented by these instances. Finally we look at how the density of subformulae can influence the hardness of SAT instances.

Place, publisher, year, edition, pages
2006. Vol. 2
URN: urn:nbn:se:umu:diva-7601OAI: diva2:147272
Available from: 2008-01-11 Created: 2008-01-11 Last updated: 2011-01-11Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Markström, Klas
By organisation
Mathematics and Mathematical Statistics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 24 hits
ReferencesLink to record
Permanent link

Direct link