Tractability and Learnability Arising from Algebras with Few Subpowers
From MaRDI portal
Publication:5390586
DOI10.1137/090775646zbMath1216.68129MaRDI QIDQ5390586
Paweł M. Idziak, Ralph McKenzie, Petar Marković, Ross Willard, Matthew A. Valeriote
Publication date: 4 April 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/090775646
complexity; polymorphism; constraint satisfaction; near-unanimity; few subpowers; learnability; Mal'tsev operations; polynomially expressive
68Q32: Computational learning theory
68Q25: Analysis of algorithms and problem complexity
08A70: Applications of universal algebra in computer science
Related Items
Unnamed Item, Proof Complexity Meets Algebra, ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM, Unnamed Item, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side, Satisfiability in MultiValued Circuits, Hybrid Tractable Classes of Constraint Problems, The Complexity of Valued CSPs, Backdoor Sets for CSP., Algebra and the Complexity of Digraph CSPs: a Survey, Unnamed Item, Constant-Query Testability of Assignments to Constraint Satisfaction Problems, The Power of Linear Programming for General-Valued CSPs, The Complexity of General-Valued CSPs, Complexity and polymorphisms for digraph constraint problems under some basic constructions, The subpower membership problem for semigroups, Binarisation for Valued Constraint Satisfaction Problems, Recent Results on the Algebraic Approach to the CSP, Dualities for Constraint Satisfaction Problems, Constraint Satisfaction Problems with Infinite Templates, Between an n-ary and an n + 1-ary near-unanimity term, CLAP: A New Algorithm for Promise CSPs, Vaughan-Lee's nilpotent loop of size 12 is finitely based, Tractability in constraint satisfaction problems: a survey, Dualities and algebras with a near-unanimity term, Finitely related clones and algebras with cube terms., Reflexive digraphs with near unanimity polymorphisms, Colouring, constraint satisfaction, and complexity, On the number of finite algebraic structures, An algebraic hardness criterion for surjective constraint satisfaction., Mal'tsev conditions, lack of absorption, and solvability., On the expression complexity of equivalence and isomorphism of primitive positive formulas, Backdoors into heterogeneous classes of SAT and CSP, Conservative constraint satisfaction re-revisited, There are no pure relational width 2 constraint satisfaction problems, The subpower membership problem for bands, Cube term blockers without finiteness, On singleton arc consistency for CSPs defined by monotone patterns, Generic expression hardness results for primitive positive formula comparison, Existence of cube terms in finite algebras, Constraint satisfaction problems over semilattice block Mal'tsev algebras, Commutative idempotent groupoids and the constraint satisfaction problem., Dichotomy for finite tournaments of mixed-type, On finite Taylor algebras, On the CSP Dichotomy Conjecture, Constraint Satisfaction Problems Solvable by Local Consistency Methods, On Singleton Arc Consistency for CSPs Defined by Monotone Patterns, Non-dichotomies in Constraint Satisfaction Complexity, Quantified Constraint Satisfaction and the Polynomially Generated Powers Property, Varieties with few subalgebras of powers
