An assertion concerning functionally complete algebras and NP-completeness

DOI10.1016/J.TCS.2008.08.028MaRDI QIDQ955041zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(12)

• Constructions of polynomially complete quasigroups of arbitrary order
• Applications of quasigroups to cryprography
• 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
• Efficient verification of polynomial completeness of quasigroups
• Format-preserving encryption: a survey
• Symmetry structure in discrete models of biochemical systems: natural subsystems and the weak control hierarchy in a new model of computation driven by interactions
• Quasigroups and their applications
• 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)