Summary: \(k\)-CNF is the class of CNF formulas in which the length of each clause of every formula is \(k\). The decision problem asks for an assignment of truth values to the variables that satisfies all the clauses of a given CNF formula. The \(k\)-SAT problem is the \(k\)-CNF decision problem. Cook has shown that \(k\)-SAT is NP-complete for \(k \geq 3\). LCNF is the class of linear formulas and LSAT is its decision problem. In [Q. Zhang and D. Xu, “The existence of unsatisfiable formulas in \(k\)-LCNF for \(k \geq 3\)”, Lect. Notes Comput. Sci. 4484, 616–623 (2007; Zbl 1200.68129)] we presented a general method to construct linear minimal unsatisfiable (MU) formulas. \(\text{NP} = \text{PCP}(\log ,1)\) is called the PCP theorem, and this is equivalent to the property that there exists some \(r > 1\) such that (3SAT, \(r\)-UN3SAT) (also denoted by \((1-\frac{1}{r})\)-GAP3SAT) is NP-complete. In this paper,we show that for \(k \geq 3\), (\(k\)-SAT, \(r\)-UN\(k\)SAT) is NP-complete and (LSAT, \(r\)-UNLSAT) is NP-complete for some \(r > 1\). Based on the application of linear MU formulas, in [loc. cit.] we constructed a reduction from (4SAT, \(r\)-UN4SAT) to (LSAT\(_{ \geq 4}\), \(r^{\prime}\)-UNLSAT\(_{ \geq 4}\)), and proved that (LSAT\(_{ \geq 4}\), \(r\)-UNLSAT\(_{ \geq 4}\)) is NP-complete for some \(r > 1\), so the approximation problem \(s\)-Approx-LSAT\(_{ \geq 4}\) is NP-hard for some \(s > 1\).
For the entire collection see [Zbl 1137.68012].