THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA

DOI10.1017/bsl.2015.25zbMath1336.68113OpenAlexW2285982983MaRDI QIDQ2795309

Libor Barto

Publication date: 21 March 2016

Published in: The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/bsl.2015.25

zbMATH Keywords

constraint satisfaction problemuniversal algebra

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Equational logic, Mal'tsev conditions (08B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (17)

On a stronger reconstruction notion for monoids and clones ⋮ Axiomatisability and hardness for universal Horn classes of hypergraphs ⋮ Ideal Membership Problem over 3-Element CSPs with Dual Discriminator Polymorphism ⋮ Unnamed Item ⋮ Universal algebraic methods for non-classical logics ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ The wonderland of reflections ⋮ Proof Complexity Meets Algebra ⋮ Unnamed Item ⋮ The Complexity of Valued CSPs ⋮ Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond ⋮ Unnamed Item ⋮ Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems) ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ MALTSEV CONDITIONS FOR GENERAL CONGRUENCE MEET-SEMIDISTRIBUTIVE ALGEBRAS

Cites Work

• Unnamed Item
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• Bounded width problems and algebras
• Existence theorems for weakly symmetric operations
• Universal algebra and hardness results for constraint satisfaction problems
• CD(4) has bounded width
• The method of forced enumeration for nondeterministic automata
• On the complexity of H-coloring
• On the algebraic structure of combinatorial problems
• Combinatorial problems raised from 2-semilattices
• Closed systems of functions and predicates
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• Meditations on Quantified Constraint Satisfaction
• Varieties with few subalgebras of powers
• Nondeterministic Space is Closed under Complementation
• Structure and importance of logspace-MOD class
• On the Structure of Polynomial Time Reducibility
• Varieties Obeying Homotopy Laws
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• Computational Complexity
• An Algebraic Theory of Complexity for Discrete Optimization
• A Simple Algorithm for Mal'tsev Constraints

This page was built for publication: THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA