[FOM] Question about satisfiability

[Daniel Leivant]

] 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.

The problem of interest is satisfying at least k clauses in a 
*** 2CNF formula ***,
i.e. with at most 2 literals in each disjunctive clause.
Otherwise 3CNF satisfiability is a special case of the above.

] 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). 

Here the problem is non-trivial even for 3-clauses.  But it seems
NP complete already for 2CNF.

Let G[x,y,z] be the 2CNF gadget
	(x v -y) (y v -z) (z v -x)
If a valuation V satisfies all or none of x,y,z, then it satisfies 
all three clauses above.  Otherwise V satisfies exactly two.

Given a 3CNF formula F with c clauses, let F' be the 2CNF formula with
3c clauses, obtained by replacing each clause AvBvC of F by G[A,B,C].
Thus every valuation satisfies at least 2c clauses of F'.

A valuation V NAE-satisfies F (i.e. satisfies 1 or 2 of the literals
in each 3-clause, but not all three), iff V satisfies at most 2c
(i.e. exactly 2c) of the 3c clauses of F'.  

Since NAE-3CNF satisfiability is NP complete, so is the given problem.

cheers - dl