TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS

DOI10.1142/S0218196706003116zbMath1100.08004MaRDI QIDQ5483456

Benoit Larose, László Zádori

Publication date: 14 August 2006

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

zbMATH Keywords

computational complexitysystems of polynomial equationsconstraint satisfactionvarieties of algebras

Mathematics Subject Classification ID

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) Congruence modularity, congruence distributivity (08B10)

Related Items (16)

Tractability in constraint satisfaction problems: a survey ⋮ Loosely-abelian algebras ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Satisfiability in MultiValued Circuits ⋮ Unnamed Item ⋮ Efficient verification of polynomial completeness of quasigroups ⋮ SOLVABILITY OF SYSTEMS OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS ⋮ Quantified Constraints in Twenty Seventeen ⋮ Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras. ⋮ An assertion concerning functionally complete algebras and NP-completeness ⋮ On solvability of systems of polynomial equations ⋮ Unnamed Item ⋮ TERM EQUATION SATISFIABILITY OVER FINITE ALGEBRAS ⋮ Dichotomy for finite tournaments of mixed-type ⋮ Robustly Solvable Constraint Satisfaction Problems ⋮ THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS

Cites Work

• Unnamed Item
• The number of non-isomorphic models in quasi-varieties of semigroups
• Unary polynomials in algebras. I
• Laws obeyed by topological algebras - extending results of Hopf and Adams
• Polynomial interpolation and the Chinese remainder theorem for algebraic systems
• Constraints, consistency and closure
• On the algebraic structure of combinatorial problems
• Semigroups obeying the term condition
• Conjunctive-query containment and constraint satisfaction
• Congruence join semidistributivity is equivalent to a congruence identity.
• The complexity of solving equations over finite groups
• Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem
• Dichotomies for classes of homomorphism problems involving unary functions
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Varieties Obeying Homotopy Laws
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Complexity of the Extendibility Problem for Finite Posets
• Classifying the Complexity of Constraints Using Finite Algebras

This page was built for publication: TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS