One more occurrence of variables makes satisfiability jump from trivial to NP-complete

• Published in: SIAM journal on computing 1993-02, Vol.22 (1), p.203-210
• Main Authors: Kratochvil, Jan, Savicky, Petr, Tuza, Zsolt
• Format: Article
• Language: English
• Subjects: Applied sciences; Boolean; Exact sciences and technology; Flows in networks. Combinatorial problems; Operational research and scientific management; Operational research. Management science; Variables
• ISSN: 0097-5397; 1095-7111
• DOI: 10.1137/0222015

A Boolean formula in a conjunctive normal form is called a $(k,s)$ - formula if every clause contains exactly $k$ variables and every variable occurs in at most $s$ clauses. The $(k,s)$-${\text{SAT}}$ problem is the SATISFIABILITY problem restricted to $(k,s)$-formulas. It is proved that for every $k \geqslant 3$ there is an integer $f(k)$ such that $(k,s)$-${\text{SAT}}$ is trivial for $s \leqslant f(k)$ (because every $(k,s)$-formula is satisfiable) and is NP-complete for $s \geqslant f(k) + 1$. Moreover, $f(k)$ grows exponentially with $k$, namely, $\lfloor {{{2^k } / {ek}}} \rfloor \leqslant f(k) \leqslant 2^{k - 1} - 2^{k - 4} - 1$ for $k \geqslant 4$.