Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
From MaRDI portal
Publication:2881074
DOI10.2168/LMCS-8(1:7)2012zbMath1239.08002arXiv1201.0557OpenAlexW2102459557MaRDI QIDQ2881074
Publication date: 3 April 2012
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1201.0557
Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
In praise of homomorphisms ⋮ The Complexity of General-Valued CSPs ⋮ Small Promise CSPs that reduce to large CSPs ⋮ Algebraic Properties of Valued Constraint Satisfaction Problem ⋮ Tropically convex constraint satisfaction ⋮ Complexity and polymorphisms for digraph constraint problems under some basic constructions ⋮ Galois theory for semiclones ⋮ Constraint Satisfaction Problems Solvable by Local Consistency Methods ⋮ Axiomatisability and hardness for universal Horn classes of hypergraphs ⋮ Deciding absorption in relational structures ⋮ Absorption and directed Jónsson terms ⋮ Hardness of Network Satisfaction for Relation Algebras with Normal Representations ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The smallest hard trees ⋮ Constraint satisfaction problem: what makes the problem easy ⋮ Some structural and residual properties of 2-semilattices ⋮ The wonderland of reflections ⋮ Taylor term does not imply any nontrivial linear one-equality Maltsev condition ⋮ The existence of a near-unanimity function is decidable ⋮ Unnamed Item ⋮ The Complexity of Valued CSPs ⋮ The structure of polynomial operations associated with smooth digraphs. ⋮ A juggler's dozen of easy\(^\dag\) problems (\(^\dag\) Well, easily formulated \dots). ⋮ Mal'tsev conditions, lack of absorption, and solvability. ⋮ Solving equation systems in ω-categorical algebras ⋮ Max-Closed Semilinear Constraint Satisfaction ⋮ Loop conditions ⋮ Decidability of absorption in relational structures of bounded width. ⋮ Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties. ⋮ Pseudo‐loop conditions ⋮ A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP ⋮ Loop conditions for strongly connected digraphs ⋮ The local loop lemma ⋮ Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems) ⋮ On algebras with many symmetric operations ⋮ The number of clones determined by disjunctions of unary relations ⋮ A Dichotomy for First-Order Reducts of Unary Structures ⋮ Hedetniemi's Conjecture and Strongly Multiplicative Graphs ⋮ Unnamed Item ⋮ Characterizations of several Maltsev conditions. ⋮ Testing for edge terms is decidable ⋮ A quasi-Mal'cev condition with unexpected application. ⋮ Menger systems of idempotent cyclic and weak near-unanimity multiplace functions
This page was built for publication: Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
