The Minimum Satisfiability Problem
Rajeev Kohli, Ramesh Krishnamurti, Prakash Mirchandani · SIAM Journal on Discrete Mathematics · 1994
This paper shows that a minimization version of satisfiability is strongly NP-hard, even if each clause contains no more than two literals and/or each clause contains at most one unnegated variable. The worst-case and average-case performances of greedy and probabilistic greedy heuristics for the problem are examined, and tight upper bounds on the performance ratio in each case are developed.