Reference : A complexity index for satisfiability problems
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
A complexity index for satisfiability problems
Boros, Endre []
Crama, Yves mailto [Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production >]
Hammer, Peter L. []
Saks, Mike []
SIAM Journal on Computing
Society for Industrial & Applied Mathematics
Yes (verified by ORBi)
[en] Boolean satisfiability ; polynomial algorithms ; NP completeness
[en] This paper associates a linear programming problem (LP) to any conjunctive normal form p, and shows that the optimum value Z(p) of this LP measures the complexity of the corresponding SAT (Boolean satisfiability) problem. More precisely, there is an algorithm for SAT that runs in polynomial time on the class of satisfiability problems satisfying Z(p) \leq 1 + \frac{c \log n}{n} for a fixed constant c, where n is the number of variables. In contrast, for any fixed \beta < 1, SAT is still NP-complete when restricted to the class of CNFs for which Z(p) \leq 1 + (1/n^\beta ).

File(s) associated to this reference

Fulltext file(s):

Restricted access
Complexity index.pdfPublisher postprint535.05 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.