The Next Whisky Bar

Mike Behrisch (1) , Miki Hermann (2) , Stefan Mengel (3) , Gernot Salzer (4)

1 TU Dresden - Technische Universität Dresden = Dresden University of Technology
2 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
3 CRIL - Centre de Recherche en Informatique de Lens
4 Institut für Computersprachen

We determine the complexity of an optimization problem related to information theory. Taking a conjunctive propositional formula over some finite set of Boolean relations as input, we seek a satisfying assignment of the formula having minimal Hamming distance to a given assignment that is not required to be a model (NearestSolution, NSol). We obtain a complete classification with respect to the relations admitted in the formula. For two classes of constraint languages we present polynomial time algorithms; otherwise, we prove hardness or completeness concerning the classes APX, poly-APX, NPO, or equivalence to well-known hard optimization problems.

Domains: Artificial Intelligence [cs.AI]

Mike Behrisch, Miki Hermann, Stefan Mengel, Gernot Salzer. The Next Whisky Bar. 11th International Computer Science Symposium in Russia (CSR'16), 2016, St. Petersburg, Russia. pp.41--56. ⟨hal-03301002⟩