[FOM] Question about satisfiability
Kreinovich, Vladik
vladik at utep.edu
Tue Sep 4 10:27:48 EDT 2007
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?
(If it is, then some problems of data processing in the presence of
outliers are also NP-hard).
More information about the FOM
mailing list