Algebraic approach to promise constraint satisfaction

Abstract

The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the last 20 years. A new version of the CSP, the promise CSP (PCSP) has recently been proposed, motivated by open questions about the approximability of variants of satisfiability and graph colouring. The PCSP significantly extends the standard decision CSP. The complexity of CSPs with a fixed constraint language on a finite domain has recently been fully classified, greatly guided by the algebraic approach, which uses polymorphisms --- high-dimensional symmetries of solution spaces --- to analyse the complexity of problems. The corresponding classification for PCSPs is wide open and includes some long-standing open questions, such as the complexity of approximate graph colouring, as special cases. The basic algebraic approach to PCSP was initiated by Brakensiek and Guruswami, and in this paper we significantly extend it and lift it from concrete properties of polymorphisms to their abstract properties. We introduce a new class of problems that can be viewed as algebraic versions of the (Gap) Label Cover problem, and show that every PCSP with a fixed constraint language is equivalent to a problem of this form. This allows us to identify a "measure of symmetry" that is well suited for comparing and relating the complexity of different PCSPs via the algebraic approach. We demonstrate how our theory can be applied by improving the state-of-the-art in approximate graph colouring: we show that, for any $k\ge 3$, it is NP-hard to find a $(2k-1)$-colouring of a given $k$-colourable graph.

Extended version (73 pages). Preliminary versions of parts of this paper were published in the proceedings of STOC 2019 and LICS 2019

References in corpus (7)

• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• The complexity of finite-valued CSPs
• The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs
• The weakest nontrivial idempotent equations
• The complexity of 3-colouring $H$-colourable graphs
• Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
• Algebraic and model theoretic methods in constraint satisfaction

Cited by in corpus (29)

• Improved hardness for H-colourings of G-colourable graphs
• CLAP: A New Algorithm for Promise CSPs
• The complexity of 3-colouring $H$-colourable graphs
• Conditional Dichotomy of Boolean Ordered Promise CSPs
• Local consistency as a reduction between constraint satisfaction problems
• An invitation to the promise constraint satisfaction problem
• Linearly ordered colourings of hypergraphs
• Beyond PCSP (1-in-3,NAE)
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• Smooth digraphs modulo primitive positive constructability and cyclic loop conditions
• Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
• Near-unanimity-closed minions of Boolean functions
• Promises Make Finite (Constraint Satisfaction) Problems Infinitary
• Small Promise CSPs that reduce to large CSPs
• Clonoids of Boolean functions with a monotone or discriminator source clone
• On the complexity of symmetric vs. functional PCSPs
• Constraint Satisfaction Problems over Finite Structures
• Topology and adjunction in promise constraint satisfaction
• Clonoids of Boolean functions with essentially unary, linear, semilattice, or 0- or 1-separating source and target clones
• Injective hardness condition for PCSPs
• Flexible constraint satisfiability and a problem in semigroup theory
• Approximate Graph Colouring and the Crystal with a Hollow Shadow
• Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps
• Accessible set endofunctors are universal
• Solving promise equations over monoids and groups
• Hierarchies of Minion Tests for PCSPs through Tensors
• 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
• Clonoids of Boolean functions with a linear source clone and a semilattice or 0- or 1-separating target clone
• Reflections and powers of multisorted minions