[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