Algebra Seminar talk
2016-03-18
Mike Behrisch
Minimum Hamming Distance of Boolean Propositional Models
Abstract:
We study the minimum Hamming distance between distinct satisfying
assignments of a conjunctive input formula over a given set of
Boolean relations (MinSolutionDistance, MSD). We present a
complete classification of the complexity of this optimization
problem with respect to the relations admitted in the formula. We
give polynomial time algorithms for several classes of constraint
languages. For all other cases we prove hardness or completeness
with respect to poly-APX, or NPO, or equivalence to a well-known
hard optimization problem.
This is joint work with Miki Hermann, Stefan Mengel, and Gernot Salzer. Supported by FWF grant I836-N23, ANR-11-ISO2-003-01 Blanc International grant ALCOCLAN, and QUALCOMM grant