The Role of Redundant Clauses in Solving Satisfiability Problems

From Tetherless World Wiki

Jump to: navigation, search

Citation: Honglei Zeng and Sheila A. McIlraith. (2005) The Role of Redundant Clauses in Solving Satisfiability Problems. In (extended abstract), CP-2005 (the Eleventh International Conference on Principles and Practice of Constraint Programming), October,2005.

Publication inproceedings ( Edit )
type InProceedings
bibtype inproceedings
Bibtex basics
author Honglei Zeng and Sheila A. McIlraith
title The Role of Redundant Clauses in Solving Satisfiability Problems
booktitle (extended abstract), CP-2005 (the Eleventh International Conference on Principles and Practice of Constraint Programming)
address Barcelona, Spain.
year 2005
month October
Bibtex more
Access Paper
abstract In this paper, we introduce the notion of redundant clauses to characterize the structure of SAT instances. We identify several interesting features of redundant clauses that provide compelling evidence of the correlation between the percentage of redundant clauses and the hardness of instances. We propose a definition of weighted clause-to-variable ratio (WCV), which substantially improves the classic clause-to-variable (m/n) ratio in predicting search cost and explaining phase phenomenon.

KSL Technical Report ID: KSL-05-10
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 to characterize the structure of SAT instances. We identify several interesting features of redundant clauses that provide compelling evidence of the correlation between the percentage of redundant clauses and the hardness of instances. We propose a definition of weighted clause-to-variable ratio (WCV), which substantially improves the classic clause-to-variable (m/n) ratio in predicting search 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)  +
Has author Honglei Zeng and Sheila A. McIlraith  +
Has identifier KSL-05-10  +
Has publishing details October,2005  +
Has title The Role of Redundant Clauses in Solving Satisfiability Problems  +
Has where published (extended abstract), CP-2005 (the Eleventh International Conference on Principles and Practice of Constraint Programming)  +
Has year 2005  +
Ksl tr id KSL-05-10  +
Month October  +
Process note NO  +
Title The Role of Redundant Clauses in Solving Satisfiability Problems  +
Year 2005  +
Retrieved from "http://tw.rpi.edu/wiki/The_Role_of_Redundant_Clauses_in_Solving_Satisfiability_Problems"