KSL-06-01 + redirect page
Experimental Results on the Satisfiable Core in Random 3SAT + Has identifier
Experimental Results on the Satisfiable Core in Random 3SAT + Ksl tr id
| Experimental Results on the Satisfiable Core in Random 3SAT |
Bibtype
inproceedings
Has publishing details
January,2006
Has title
Experimental Results on the Satisfiable Core in Random 3SAT
Has where published
Ninth International Symposium on Artificial Intelligence and Mathematics
Has year
2006
Title
Experimental Results on the Satisfiable Core in Random 3SAT
Year
2006
Abstract
Given a satisfiable k-CNF SAT instance, a … Given a satisfiable k-CNF SAT instance, a satisfiable core is a minimal subset of the k-CNF clauses that preserves all and only the satisfying assignments of the original instance. In this paper,we extend the previous results on satisfiable core, especially on the strong correlation between the hardness of SAT instances and the size of their satisfiable cores. We introduce a measure called the weighted clause-to-variable ratio, which substantially improves on the classic clause-to-variable ratio in explaining the phase transition. We also examine interesting transitions in satisfiable core size of random instances and show that satisfiable core is a powerful concept for studying the constrainedness of instances. studying the constrainedness of instances.
Address
Fort Lauderdale, Florida, USA +
Author
Honglei Zeng and Sheila A. McIlraith +
Booktitle
Ninth International Symposium on Artificial Intelligence and Mathematics +
Has author
Honglei Zeng and Sheila A. McIlraith +
Has identifier
Experimental Results on the Satisfiable Core in Random 3SAT +
Ksl tr id
Experimental Results on the Satisfiable Core in Random 3SAT +
Month
January +
Process note
NO +
Categories InProceedings +, KSL Technical Report +, Publication +
|
