TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
DOI10.1142/S0218196706003116zbMATH Open1100.08004MaRDI QIDQ5483456FDOQ5483456
Authors: Benoît Larose, L. Zádori 
Publication date: 14 August 2006
Published in: International Journal of Algebra and Computation (Search for Journal in Brave)
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Congruence modularity, congruence distributivity (08B10) Applications of universal algebra in computer science (08A70)
Cites Work
- Title not available (Why is that?)
- Complexity classifications of Boolean constraint satisfaction problems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Classifying the Complexity of Constraints Using Finite Algebras
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- Conjunctive-query containment and constraint satisfaction
- Polynomial interpolation and the Chinese remainder theorem for algebraic systems
- Semigroups obeying the term condition
- The complexity of solving equations over finite groups
- The Complexity of the Extendibility Problem for Finite Posets
- Congruence join semidistributivity is equivalent to a congruence identity.
- Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem
- Dichotomies for classes of homomorphism problems involving unary functions
- Varieties Obeying Homotopy Laws
- Unary polynomials in algebras. I
- The number of non-isomorphic models in quasi-varieties of semigroups
- Laws obeyed by topological algebras - extending results of Hopf and Adams
Cited In (28)
- An assertion concerning functionally complete algebras and NP-completeness
- The complexity of the equivalence problem over finite rings.
- Expressive power, satisfiability and equivalence of circuits over nilpotent algebras
- Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
- SOLVABILITY OF SYSTEMS OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
- Tractability in constraint satisfaction problems: a survey
- Computational complexity of solving equation systems
- Computing and Combinatorics
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dichotomy for finite tournaments of mixed-type
- Quantified Constraints in Twenty Seventeen
- Loosely-abelian algebras
- Strongly-local reductions and the complexity/efficient approximability of algebra and optimization on abstract algebraic structures
- Efficient verification of polynomial completeness of quasigroups
- Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture
- Solving equations over small unary algebras
- Satisfiability in multi-valued circuits
- Satisfiability in MultiValued Circuits
- Title not available (Why is that?)
- Term equation satisfiability over finite algebras
- On complexity of solving of equations over graphs
- Hard constraint satisfaction problems have hard gaps at location 1
- On solvability of systems of polynomial equations
- On complexity of the satisfiability problem of systems over finite posets
- Polynomial constraints and unsat cores in \textsc{Tarski}
- Robustly solvable constraint satisfaction problems
- THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
This page was built for publication: TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5483456)
