The role of redundant clauses in solving satisfiability problems
From Semantic Portal Wiki
{{#vardefine:category|Publication}}{{#vardefine:templatename|i.publication}}{{#vardefine:package|smwbp_instance_templates}}
| Edit |
Reference: {{#vardefine:pagename|the role of redundant clauses in solving satisfiability problems }}
- [[]]
bibtex
{{#vardefine:pagename|The role of redundant clauses in solving satisfiability problems }}{{#vardefine:key| }}
abstract: In this paper, we introduce the notion of redundant clauses tocharacterize the structure of SAT instances. We identify severalinteresting features of redundant clauses that provide compellingevidence of the correlation between the percentage of redundantclauses and the hardness of instances. We propose a definition ofweighted clause-to-variable ratio (WCV), which substantiallyimproves the classic clause-to-variable (m/n) ratio in predictingsearch cost and explaining phase phenomenon.
download:
- paper:
- slides:
Facts about The role of redundant clauses in solving satisfiability problemsRDF feed
| Abstract | In this paper, we introduce the notion of … In this paper, we introduce the notion of redundant clauses tocharacterize the structure of SAT instances. We identify severalinteresting features of redundant clauses that provide compellingevidence of the correlation between the percentage of redundantclauses and the hardness of instances. We propose a definition ofweighted clause-to-variable ratio (WCV), which substantiallyimproves the classic clause-to-variable (m/n) ratio in predictingsearch cost and explaining phase phenomenon. arch cost and explaining phase phenomenon. |
| Address | Barcelona, Spain. + |
| Author | Honglei Zeng +, and Sheila A. McIlraith + |
| Bibtype | inproceedings + |
| Booktitle | (extended abstract), CP-2005 (the Eleventh International Conference on Principles and Practice of Constraint Programming) + |
| Key | KSL-05-10 + |
| Month | October + |
| Tag | Computer science + |
| Title | The Role of Redundant Clauses in Solving Satisfiability Problems + |
| Tr id | KSL-05-10 + |
| Year | 2005 + |
