An assertion concerning functionally complete algebras and NP-completeness

DOI10.1016/J.TCS.2008.08.028zbMATH Open1153.68020OpenAlexW2061999747MaRDI QIDQ955041FDOQ955041

Authors: Gábor Horváth, Chrystopher L. Nehaniv, Csaba Szabó 

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2437/114142

Recommendations

• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• Publication:4729350
• The complexity of problems connected with two-element algebras
• Solving equations over small unary algebras
• Term equation satisfiability over finite algebras

zbMATH Keywords

NP-completenesscoNP-completenesssolvability of equationsfunctionally complete algebrasidentity checkingsolvability of systems of equations

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Applications of universal algebra in computer science (08A70)

Cites Work

• Title not available (Why is that?)
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• The equivalence problem for finite rings
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
• Results on the equivalence problem for finite groups.
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• The complexity of the equivalence problem for nonsolvable groups
• The complexity of equivalence for commutative rings
• Unification in primal algebras, their powers and their varieties
• MONOIDS AND COMPUTATIONS

Cited In (12)

• Constructions of polynomially complete quasigroups of arbitrary order
• Algebraic properties of subquasigroups and construction of finite quasigroups
• Strong polynomial completeness of almost all quasigroups
• Automorphisms of finite quasi-groups without sub-quasi-groups
• Functional completeness criteria in Dijkstra algebra
• Algorithms for checking some properties of \(n\)-quasigroups
• Format-preserving encryption: a survey
• Efficient verification of polynomial completeness of quasigroups
• Квазигруппы и их приложения
• Symmetry structure in discrete models of biochemical systems: natural subsystems and the weak control hierarchy in a new model of computation driven by interactions
• Title not available (Why is that?)
• Polynomially complete quasigroups of prime order

This page was built for publication: An assertion concerning functionally complete algebras and NP-completeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q955041)