[FOM] Question about satisfiability

[Tjark Weber]

On Thursday 06 September 2007 13:59, Tjark Weber wrote:
> > 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.

Unfortunately this quick remark doesn't solve the problem in question, as 
Vladik (and another reader of this list) kindly pointed out to me.  I retract 
my statement.

Tjark