A Proof of the CSP Dichotomy Conjecture
From MaRDI portal
Publication:5133982
DOI10.1145/3402029zbMath1491.68128arXiv1704.01914OpenAlexW3081785465WikidataQ123197481 ScholiaQ123197481MaRDI QIDQ5133982
Publication date: 11 November 2020
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1704.01914
computational complexityconstraint satisfaction problemrelational clonesweak near-unanimityCSP dichotomy
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Applications of universal algebra in computer science (08A70) Operations and polynomials in algebraic structures, primal algebras (08A40) Computational aspects of satisfiability (68R07)
Related Items
On a stronger reconstruction notion for monoids and clones, On regularity of Max-CSPs and Min-CSPs, CLAP: A New Algorithm for Promise CSPs, Topology and Adjunction in Promise Constraint Satisfaction, Universal Horn Sentences and the Joint Embedding Property, Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting), Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity, The lattice and semigroup structure of multipermutations, When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems, Correspondence homomorphisms to reflexive graphs, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, Complexity of correspondence \(H\)-colourings, The 2-colouring problem for $(m,n)$-mixed graphs with switching is polynomial, Unnamed Item, The smallest hard trees, The algebraic structure of the densification and the sparsification tasks for CSPs, \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's, Constraint satisfaction problem: what makes the problem easy, Mixing is hard for triangle-free reflexive graphs, On guarded extensions of MMSNP, Solving infinite-domain CSPs using the patchwork property, The complexity of the matroid homomorphism problem, Recolouring homomorphisms to triangle-free reflexive graphs, Computing a partition function of a generalized pattern-based energy over a semiring, Unnamed Item, General lower bounds and improved algorithms for infinite-domain CSPs, Proof Complexity Meets Algebra, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems, Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms, Sandwiches for promise constraint satisfaction, Constraint satisfaction problems over semilattice block Mal'tsev algebras, Unnamed Item, Galois connections for patterns: an algebra of labelled graphs, The number of clones determined by disjunctions of unary relations, Time Complexity of Constraint Satisfaction via Universal Algebra, Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices, A Dichotomy for First-Order Reducts of Unary Structures, Beyond PCSP (\textbf{1-in-3}, \textbf{NAE}), Unnamed Item, Computational Short Cuts in Infinite Domain Constraint Satisfaction, The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side, The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
