[FOM] Question about satisfiability

[Tjark Weber]

On Tuesday 04 September 2007 16:27, Kreinovich, Vladik wrote:
> It is known that not only propositional satisfiability is NP-hard for
> CNF formulas F, but also the problem of finding a Boolean vector which
> satisfies at least k clauses of a given formula is, in general, NP-hard.
>
> 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?

I think so.  Suppose v is a Boolean vector which satisfies at most k clauses 
of F, where F contains n clauses total.  Then \neg v satisfies at least n-k 
clauses of F.

Best,
Tjark