On Linear CNF Formulas

摘要

In the present paper we introduce the class of linear CNF formulas generalizing the notion of linear hypergraphs. Clauses of a linear formula intersect in at most one variable. We show that SAT for the general class of linear formulas remains NP-complete. Moreover we show that the subclass of exactly linear formulas is always satisfiable. We further consider the class of uniform linear formulas and investigate conditions for the formula graph to be complete. We define a formula hierarchy such that one can construct a 3-uniform linear formula belonging to the ith level such that the clause-variable density is of Ω(2.5~(i-1))∩O(3.2~(i-1)). Finally, we introduce the subclasses LCNF_(≥k) of linear formulas having only clauses of length at least k, and show that SAT remains NP-complete for LCNF_(≥3).