Tractability and Learnability Arising from Algebras with Few Subpowers
From MaRDI portal
Publication:5390586
DOI10.1137/090775646zbMath1216.68129OpenAlexW2052726983MaRDI 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
complexitypolymorphismconstraint satisfactionnear-unanimityfew subpowerslearnabilityMal'tsev operationspolynomially expressive
Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70)
Related Items (51)
Tractability in constraint satisfaction problems: a survey ⋮ CLAP: A New Algorithm for Promise CSPs ⋮ The Complexity of General-Valued CSPs ⋮ Complexity and polymorphisms for digraph constraint problems under some basic constructions ⋮ The subpower membership problem for semigroups ⋮ Dualities and algebras with a near-unanimity term ⋮ Constraint Satisfaction Problems Solvable by Local Consistency Methods ⋮ Satisfiability in MultiValued Circuits ⋮ On Singleton Arc Consistency for CSPs Defined by Monotone Patterns ⋮ The subpower membership problem for bands ⋮ Unnamed Item ⋮ Cube term blockers without finiteness ⋮ On finite Taylor algebras ⋮ Conservative constraint satisfaction re-revisited ⋮ Constraint satisfaction problem: what makes the problem easy ⋮ Vaughan-Lee's nilpotent loop of size 12 is finitely based ⋮ Non-dichotomies in Constraint Satisfaction Complexity ⋮ Quantified Constraint Satisfaction and the Polynomially Generated Powers Property ⋮ Finitely related clones and algebras with cube terms. ⋮ Generic expression hardness results for primitive positive formula comparison ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ Reflexive digraphs with near unanimity polymorphisms ⋮ Proof Complexity Meets Algebra ⋮ Colouring, constraint satisfaction, and complexity ⋮ On the number of finite algebraic structures ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ The Complexity of Valued CSPs ⋮ Backdoor Sets for CSP. ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Existence of cube terms in finite algebras ⋮ An algebraic hardness criterion for surjective constraint satisfaction. ⋮ Varieties with few subalgebras of powers ⋮ Mal'tsev conditions, lack of absorption, and solvability. ⋮ On singleton arc consistency for CSPs defined by monotone patterns ⋮ On the CSP Dichotomy Conjecture ⋮ ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM ⋮ On the expression complexity of equivalence and isomorphism of primitive positive formulas ⋮ There are no pure relational width 2 constraint satisfaction problems ⋮ Constraint satisfaction problems over semilattice block Mal'tsev algebras ⋮ Backdoors into heterogeneous classes of SAT and CSP ⋮ Dichotomy for finite tournaments of mixed-type ⋮ Unnamed Item ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ Recent Results on the Algebraic Approach to the CSP ⋮ Dualities for Constraint Satisfaction Problems ⋮ Constraint Satisfaction Problems with Infinite Templates ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Between an n-ary and an n + 1-ary near-unanimity term ⋮ Commutative idempotent groupoids and the constraint satisfaction problem. ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
This page was built for publication: Tractability and Learnability Arising from Algebras with Few Subpowers
