Output details
11 - Computer Science and Informatics
Queen's University Belfast
Output title
Zero-One Designs Produce Small Hard SAT Instances
Type
E - Conference contribution
Name of conference/published proceedings
Theory and Applications of Satisfiability Testing – SAT 2010 : 13th International Conference, SAT 2010, Edinburgh, UK, July 11-14, 2010. Proceedings
Volume number
-
Issue number
-
First page of article
388
ISSN of proceedings
-
Year of publication
2010
URL
-
Number of additional authors
1
Additional information
<12>Some basics of combinatorial block design are combined with certain constraint satisfaction problems of interest to the satisfiability community. Such combinations can be used to generate satisfiability problems which are shown empirically to be some of the smallest very hard satisfiability problems ever constructed. This gives further rigour to the construction method used in the initial generator sgen1. A new three-dimensional form of combinatorial block design is introduced, and leads to small, very hard, satisfiable formulas. The methods are validated on solvers that performed well in the SAT 2009 and earlier competitions.
Interdisciplinary
-
Cross-referral requested
-
Research group
A - High Performance and Distributed Computing (HPDC)
Citation count
0
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
