[FOM] Question about satisfiability

[Alasdair Urquhart]

>>> 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.

Alasdair Urquhart