Linear k-SAT be the problem of deciding whether a given linear k-CNF formula is satisfiable.
Here, a k-CNF formula is a CNF formula in which every clause has size exactly k. It was
known that for k>= 3, Linear k-SAT is NP-complete if and only if an unsatisfiable linear k-
CNF formula exists, and that they do exist for k>= 4. We prove that unsatisfiable linear k-CNF
formulas exist for every k. Let f (k) be the minimum number of clauses in an unsatisfiable …