✦ LIBER ✦
The k-SATISFIABILITY problem remains NP-complete for dense families
✍ Scribed by Ingo Schiermeyer
- Publisher
- Elsevier Science
- Year
- 1994
- Tongue
- English
- Weight
- 228 KB
- Volume
- 125
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
We consider the ~ATISFIABILITY problem (~-SAT): Given a family F of n clauses cl, ._, , c, in conjunctive normal form, each consisting of k literals corresponding to k different variables of a set of r 2 k 2 1 boolean variables, is F satisfiable? By k-SAT@ no) we denote the k-SAT problem restricted to families with n > n,(r) clauses. We prove that for each k > 3 and each integer I > 4 such that r > Ik2, the k-SAT(>(;)
(2'-l-4/1))
problem is NP-complete.