An assertion concerning functionally complete algebras and NP-completeness

DOI10.1016/j.tcs.2008.08.028zbMath1153.68020OpenAlexW2061999747MaRDI QIDQ955041

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

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

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

Related Items (11)

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

Cites Work

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

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