Reference : A complexity index for satisfiability problems
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/217333
A complexity index for satisfiability problems
English
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 []
1994
SIAM Journal on Computing
Society for Industrial & Applied Mathematics
23
45-49
Yes (verified by ORBi)
0097-5397
1095-7111
[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 ).
Researchers
http://hdl.handle.net/2268/217333
10.1137/S0097539792228629

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Restricted access
Complexity index.pdfPublisher postprint535.05 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.