The role of redundant clauses in solving satisfiability problems

From Semantic Portal Wiki

Edit

Reference:

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

bibtex

@inproceedings { KSL-05-10 ,
  author = "Honglei Zeng, Sheila A. McIlraith", 
booktitle = "(extended abstract), CP-2005 (the Eleventh International Conference on Principles and Practice of Constraint Programming)", 
title = "The Role of Redundant Clauses in Solving Satisfiability Problems", 
year = "2005", 
} 

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: