[FOM] Question about satisfiability
urquhart at cs.toronto.edu
Fri Sep 7 17:04:17 EDT 2007
>>> Is it true that the problem of finding (given a CNF formula F and k) a
>>> Boolean vector which satisfies at most k clauses of F is NP-hard?
This problem was proved to be NP-complete in a 1994 paper by
Kohli, Krishnamurti and Mirchandani, entitled "The Minimum
Satisfiability Problem" (SIAM J. Discrete Math., Vol. 7,
pp. 275-283). The authors show that the problem is NP-complete,
even when restricted to formulas in 2-CNF. The proof is
by reduction from 2-MAXSAT.
The book "Complexity and Approximation" by Ausiello,
Crescenzi, Gambosi, Kann, Marchetti-Spaccamela and Protasi
(Springer 1999) has some information on the approximability
behaviour of the problem on p. 456.
More information about the FOM