Experimental results on the satisfiable core in random 3sat
From Semantic Portal Wiki
| Edit |
Reference:
- Honglei Zeng, Sheila A. McIlraith. Experimental Results on the Satisfiable Core in Random 3SAT , Ninth International Symposium on Artificial Intelligence and Mathematics, 2006
bibtex
@inproceedings { KSL-06-01 ,
author = "Honglei Zeng, Sheila A. McIlraith",
booktitle = "Ninth International Symposium on Artificial Intelligence and Mathematics",
title = "Experimental Results on the Satisfiable Core in Random 3SAT",
year = "2006",
}
abstract: Given a satisfiable k-CNF SAT instance, a satisfiable core isa minimal subset of the k-CNF clauses that preserves all and onlythe satisfying assignments of the original instance. In this paper,we extend the previous results on satisfiable core, especially onthe strong correlation between the hardness of SAT instances and thesize of their satisfiable cores. We introduce a measure called theweighted clause-to-variable ratio, which substantially improves onthe classic clause-to-variable ratio in explaining the phasetransition. We also examine interesting transitions in satisfiablecore size of random instances and show that satisfiable core is apowerful concept for studying the constrainedness of instances.
download:
- paper:
- slides:
| Abstract | Given a satisfiable k-CNF SAT instance, a … Given a satisfiable k-CNF SAT instance, a satisfiable core isa minimal subset of the k-CNF clauses that preserves all and onlythe satisfying assignments of the original instance. In this paper,we extend the previous results on satisfiable core, especially onthe strong correlation between the hardness of SAT instances and thesize of their satisfiable cores. We introduce a measure called theweighted clause-to-variable ratio, which substantially improves onthe classic clause-to-variable ratio in explaining the phasetransition. We also examine interesting transitions in satisfiablecore size of random instances and show that satisfiable core is apowerful concept for studying the constrainedness of instances. studying the constrainedness of instances. |
| Address | Fort Lauderdale, Florida, USA + |
| Author | Honglei Zeng +, and Sheila A. McIlraith + |
| Bibtype | inproceedings + |
| Booktitle | Ninth International Symposium on Artificial Intelligence and Mathematics + |
| Key | KSL-06-01 + |
| Month | January + |
| Tag | Computer science + |
| Title | Experimental Results on the Satisfiable Core in Random 3SAT + |
| Tr id | KSL-06-01 + |
| Year | 2006 + |
