×

The \(k\)-SATISFIABILITY problem remains NP-complete for dense families. (English) Zbl 0803.68052

Summary: We consider the \(k\)-SATISFIABILITY problem (\(k\)-SAT): Given a family \(F\) of \(n\) clauses \(c_ 1,\dots,c_ n\) in conjunctive normal form, each consisting of \(k\) literals corresponding to \(k\) different variables of a set of \(r\geq k\geq 1\) Boolean variables, is \(F\) satisfiable? By \(k\)-SAT \((> n_ 0)\) we denote the \(k\)-SAT problem restricted to families with \(n> n_ 0(r)\) clauses. We prove that for each \(k\geq 3\) and each integer \(l\geq 4\) such that \(r\geq lk^ 2\), the \(k\)-SAT \((>{r\choose k}(2^ k- 1- 4/l))\) problem is NP-complete.

MSC:

68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Garey, M. R.; Johnson, D. S., Computers and Intractability, (A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York) · Zbl 0369.90053
[2] Kratochvíl, J.; Savický, P.; Tuza, Z., One more occurence of variables makesSATISFIABILITY jump from trivial to NP-complete, SIAM J. Comput., 22, 203-210 (1993) · Zbl 0767.68057
[3] Schiermeyer, I., A closure concept for the \(k-\textsc{SATISFIABILITY}\) problem (1991), preprint
[4] Schiermeyer, I., Applications of the \(p\)-closure for the \(k-\textsc{SATISFIABILITY}\) problem (1991), preprint
[5] Tovey, C. A., A simplified satisfiability problem, Discrete Appl. Math., 8, 85-89 (1984) · Zbl 0534.68028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.