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.
My Menu
Saved Items

Characterizing SAT Problems with the Row Convexity Property

Hachemi BennaceurContact Information and Chu Min LiContact Information

(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

Contact Information Hachemi Bennaceur
Email: hachemi.bennaceur@lipn.univ-paris13.fr

Contact Information Chu Min Li
Email: cli@laria.u-picardie.fr
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.105 • Server: mpweb02
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)