[FOM] Question about satisfiability
Daniel Leivant
leivant at cs.indiana.edu
Fri Sep 7 20:34:34 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.
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
More information about the FOM
mailing list