[FOM] Question about satisfiability
Tjark Weber
tjark.weber at gmx.de
Thu Sep 6 07:59:57 EDT 2007
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
More information about the FOM
mailing list