The Complexity of Finite-Valued CSPs
| Autor: | Stanislav Zivny, Johan Thapper |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Department of Computer Science [Oxford], University of Oxford [Oxford], Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
FOS: Computer and information sciences
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] Reduction (recursion theory) Unary operation Computational complexity theory [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Binary number 0102 computer and information sciences 02 engineering and technology Computational Complexity (cs.CC) Computer Science::Computational Complexity [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences Domain (mathematical analysis) Combinatorics Artificial Intelligence Simple (abstract algebra) Discrete optimization 0202 electrical engineering electronic engineering information engineering Core language Constraint satisfaction problem ComputingMilieux_MISCELLANEOUS Mathematics Discrete mathematics Computer Science::Information Retrieval [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] Function (mathematics) Constraint (information theory) Linear programming relaxation Computer Science - Computational Complexity 010201 computation theory & mathematics Hardware and Architecture Control and Systems Engineering Idempotence 020201 artificial intelligence & image processing F.2.0 Software Information Systems |
| Zdroj: | Journal of the ACM (JACM) Journal of the ACM (JACM), Association for Computing Machinery, 2016, 63 (4), pp.1-33. ⟨10.1145/2974019⟩ STOC |
| ISSN: | 0004-5411 1557-735X |
| DOI: | 10.1145/2974019⟩ |
| Popis: | Let Γ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. The valued constraint satisfaction problem, VCSP(Γ), is the problem of minimising a function given as a sum of functions from Γ. We establish a dichotomy theorem with respect to exact solvability for all finite-valued languages defined on domains of arbitrary finite size. We show that every core language Γ either admits a binary idempotent and symmetric fractional polymorphism in which case the basic linear programming relaxation solves any instance of VCSP(Γ) exactly, or Γ satisfies a simple hardness condition that allows for a polynomial-time reduction from Max-Cut to VCSP(Γ). In other words, there is a single algorithm for all tractable cases and a single reason for intractability. Our results show that for exact solvability of VCSPs the basic linear programming relaxation suffices and semidefinite relaxations do not add any power. The proof uses a variation of Motzkin’s Transposition Theorem, hyperplane arrangements, and a technique recently introduced by Kolmogorov [arXiv:1207.7213] reformulated using Markov chains. Our results generalise all previous partial classifications of finite-valued languages: the classifications of {0, 1}-valued languages on two-element, three-element, and four-element domains obtained by Creignou [JCSS’95], Jonsson et al. [SICOMP’06], and Jonsson et al. [CP’11], respectively; the classification of {0, 1}-valued languages containing all unary functions obtained by Deineko et al. [JACM’06]; the classifi- cations of finite-valued languages on two-element and threeelement domains obtained by Cohen et al. [AIJ’06] and Huber et al. [SODA’13], respectively; the classification of finite- valued languages containing all {0, 1}-valued unary functions obtained by Kolmogorov and Zivn´y [SODA’12]; and ˇthe classification of Min-0-Ext problems obtained recently by Hirai [SODA’13]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|