Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Characterizing SAT Problems with the Row Convexity Property
| |
|
Characterizing SAT Problems with the Row Convexity Property
Hachemi Bennaceur5 and Chu Min Li6 
| (5) |
LIPN, Institut Galilée, Université Paris 13, Av. J.B. Clément, 93240 Villetaneuse, France |
| (6) |
LaRIA, Université de Picardie Jules Verne, 5 Rue du Moulin Neuf, 80000 Amiens, France |
Abstract
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.
This work is partially supported by French CNRS under grant number SUB/2001/0111/DR16
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|