Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy

DOI10.1137/19M128212XzbMATH Open1494.68094arXiv1704.01937OpenAlexW3212768336MaRDI QIDQ5096441FDOQ5096441

Venkatesan Guruswami, Joshua Brakensiek

Publication date: 17 August 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: A classic result due to Schaefer (1978) classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being either in $mathsfP$ or $mathsfNP$-hard. This paper considers a promise-problem variant of CSPs called PCSPs. A PCSP over a finite set of pairs of constraints $Gamma$ consists of a pair $(Ps{i}_P,Ps{i}_Q)$ of CSPs with the same set of variables such that for every $(P,Q)inGamma$, $P(x_{i_1},\mathrm{...},x_{i_k})$ is a clause of $Ps{i}_P$ if and only if $Q(x_{i_1},\mathrm{...},x_{i_k})$ is a clause of $Ps{i}_Q$. The promise problem $operatornamePCSP(Gamma)$ is to distinguish, given $(Ps{i}_P,Ps{i}_Q)$, between the cases $Ps{i}_P$ is satisfiable and $Ps{i}_Q$ is unsatisfiable. Many natural problems including approximate graph and hypergraph coloring can be placed in this framework. This paper is motivated by the pursuit of understanding the computational complexity of Boolean promise CSPs. As our main result, we show that $operatornamePCSP(Gamma)$ exhibits a dichotomy (it is either polynomial time solvable or $mathsfNP$-hard) when the relations in $Gamma$ are symmetric and allow for negations of variables. We achieve our dichotomy theorem by extending the weak polymorphism framework of Austrin, Guruswami, and Haa stad [FOCS '14] which itself is a generalization of the algebraic approach to study CSPs. In both the algorithm and hardness portions of our proof, we incorporate new ideas and techniques not utilized in the CSP case. Furthermore, we show that the computational complexity of any promise CSP (over arbitrary finite domains) is captured entirely by its weak polymorphisms, a feature known as Galois correspondence, as well as give necessary and sufficient conditions for the structure of this set of weak polymorphisms. Such insights call us to question the existence of a general dichotomy for Boolean PCSPs.

Full work available at URL: https://arxiv.org/abs/1704.01937

zbMATH Keywords

linear programmingconstraint satisfactionpolymorphismPCP theorempromise problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Applications of universal algebra in computer science (08A70) Computational aspects of satisfiability (68R07)

Cites Work

• Existence theorems for weakly symmetric operations
• On the complexity of H-coloring
• Non-dichotomies in Constraint Satisfaction Complexity
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• On the algebraic structure of combinatorial problems
• Title not available (Why is that?)
• Complexity of conservative constraint satisfaction problems
• The Complexity of Finite-Valued CSPs
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• Finitely related clones and algebras with cube terms.
• A Simple Algorithm for Mal'tsev Constraints
• Conservative constraint satisfaction re-revisited
• Title not available (Why is that?)
• Conditional Hardness for Approximate Coloring
• On the power of unique 2-prover 1-round games
• Title not available (Why is that?)
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Galois theory for minors of finite functions
• Constraint Satisfaction Problems of Bounded Width
• A finer reduction of constraint problems to digraphs
• Gap theorems for robust satisfiability: Boolean CSPs and beyond
• New hardness results for graph and hypergraph colorings
• The hardness of 3-uniform hypergraph coloring
• On the hardness of approximating the chromatic number
• On the Hardness of 4-Coloring a 3-Colorable Graph
• Title not available (Why is that?)
• $(2+\varepsilon)$-Sat Is NP-hard
• Improved hardness for H-colourings of G-colourable graphs
• A Proof of the CSP Dichotomy Conjecture
• Title not available (Why is that?)
• The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems
• Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
• Algebraic approach to promise constraint satisfaction
• An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
• Improved Hardness of Approximating Chromatic Number
• Title not available (Why is that?)

Cited In (10)

• Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
• Conditional dichotomy of Boolean ordered promise CSPs
• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
• Sandwiches for promise constraint satisfaction
• CLAP: A New Algorithm for Promise CSPs
• Topology and Adjunction in Promise Constraint Satisfaction
• Multisorted Boolean clones determined by binary relations up to minion homomorphisms
• Algebraic Approach to Promise Constraint Satisfaction
• Approximate graph colouring and the hollow shadow
• SDPs and robust satisfiability of promise CSP

This page was built for publication: Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096441)