The Minimum Satisfiability Problem
Coauthor(s): Ramesh Krishnamurti, Prakash Mirchandani.
Adobe Acrobat PDF
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.
Source: SIAM Journal on Discrete Mathematics
Kohli, Rajeev, Ramesh Krishnamurti, and Prakash Mirchandani. "The Minimum Satisfiability Problem." SIAM Journal on Discrete Mathematics 7, no. 2 (1994): 275-83.