Anzeige
Erschienen in:
2002 | OriginalPaper | Buchkapitel
Characterizing SAT Problems with the Row Convexity Property
verfasst von : Hachemi Bennaceur, Chu Min Li
Erschienen in: Principles and Practice of Constraint Programming - CP 2002
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Using the literal encoding of the satisfiability problem (SAT) as a binary constraint satisfaction problem (CSP), we relate the path consistency concept and the row convexity of CSPs with the inference rules in the propositional logic field. Then, we use this result to propose a measure characterizing satisfiable and unsatisfiable 3-SAT instances. The correlation between the computational results allows us to validate this measure.