Experimental Results on the Satisfiable Core in Random 3SAT
From Tetherless World Wiki
Citation: Honglei Zeng and Sheila A. McIlraith. (2006) Experimental Results on the Satisfiable Core in Random 3SAT. In Ninth International Symposium on Artificial Intelligence and Mathematics, January,2006.
| Publication inproceedings ( Edit ) | |
| type | InProceedings |
| bibtype | inproceedings |
| Bibtex basics | |
| author | Honglei Zeng and Sheila A. McIlraith |
| title | Experimental Results on the Satisfiable Core in Random 3SAT |
| booktitle | Ninth International Symposium on Artificial Intelligence and Mathematics |
| address | Fort Lauderdale, Florida, USA |
| year | 2006 |
| month | January |
| Bibtex more | |
| Access Paper | |
| abstract | 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. |
| KSL Technical Report ID: KSL-06-01 |
Facts about Experimental Results on the Satisfiable Core in Random 3SATRDF feed
| 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 + |
| Bibtype | inproceedings + |
| Booktitle | Ninth International Symposium on Artificial Intelligence and Mathematics + |
| Has author | Honglei Zeng and Sheila A. McIlraith + |
| Has identifier | KSL-06-01 + |
| 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 + |
| Ksl tr id | KSL-06-01 + |
| Month | January + |
| Process note | NO + |
| Title | Experimental Results on the Satisfiable Core in Random 3SAT + |
| Year | 2006 + |
