Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy

DOI10.1137/19M128212XMaRDI QIDQ5096441zbMATHOpenAlexFDO

Authors Joshua Brakensiek, Venkatesan Guruswami

Publication date 17 August 2022

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

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)

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.

Recommendations

• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• The complexity of promise SAT on non-Boolean domains
• Algebraic Approach to Promise Constraint Satisfaction
• Algebraic approach to promise constraint satisfaction
• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems

Cites work

• scientific article; zbMATH DE number 1670830 (Why is no real title available?)
• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• scientific article; zbMATH DE number 3176160 (Why is no real title available?)
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• scientific article; zbMATH DE number 7561550 (Why is no real title available?)
• A Simple Algorithm for Mal'tsev Constraints
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A finer reduction of constraint problems to digraphs
• A proof of the CSP dichotomy conjecture
• Algebraic approach to promise constraint satisfaction
• An algorithmic blend of LPs and ring equations for promise CSPs
• Classifying the Complexity of Constraints Using Finite Algebras
• Complexity of conservative constraint satisfaction problems
• Conditional Hardness for Approximate Coloring
• Conservative constraint satisfaction re-revisited
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Constraint Satisfaction Problems of Bounded Width
• Existence theorems for weakly symmetric operations
• Finitely related clones and algebras with cube terms.
• Galois theory for minors of finite functions
• Gap theorems for robust satisfiability: Boolean CSPs and beyond
• Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
• Improved hardness of approximating chromatic number
• New hardness results for graph and hypergraph colorings
• Non-dichotomies in Constraint Satisfaction Complexity
• On the Hardness of 4-Coloring a 3-Colorable Graph
• On the Structure of Polynomial Time Reducibility
• On the algebraic structure of combinatorial problems
• On the complexity of H-coloring
• On the hardness of approximating the chromatic number
• On the power of unique 2-prover 1-round games
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• The complexity of satisfiability problems
• The hardness of 3-uniform hypergraph coloring
• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
• \((2+\varepsilon)\)-Sat is NP-hard

Cited in

(16)

• Algebraic Approach to Promise Constraint Satisfaction
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• Algebraic approach to promise constraint satisfaction
• Approximate graph colouring and the hollow shadow
• SDPs and robust satisfiability of promise CSP
• Small Promise CSPs that reduce to large CSPs
• An algorithmic blend of LPs and ring equations for promise CSPs
• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
• The complexity of promise SAT on non-Boolean domains
• Multisorted Boolean clones determined by binary relations up to minion homomorphisms
• CLAP: A New Algorithm for Promise CSPs
• Topology and Adjunction in Promise Constraint Satisfaction
• 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

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)