[FOM] Question about satisfiability
Tjark Weber
tjark.weber at gmx.de
Fri Sep 7 09:23:11 EDT 2007
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
More information about the FOM
mailing list