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

coNP-completenessfunctionally complete algebrasidentity checkingNP-completenesssolvability of equationssolvability 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)

Recommendations

• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• scientific article; zbMATH DE number 4114007
• The complexity of problems connected with two-element algebras
• Solving equations over small unary algebras
• Term equation satisfiability over finite algebras

Cites work

• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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

(13)

• Polynomially complete quasigroups of prime order
• Functional completeness criteria in Dijkstra algebra
• Strong polynomial completeness of almost all quasigroups
• Algorithms for checking some properties of \(n\)-quasigroups
• Efficient verification of polynomial completeness of quasigroups
• Automorphisms of finite quasi-groups without sub-quasi-groups
• Symmetry structure in discrete models of biochemical systems: natural subsystems and the weak control hierarchy in a new model of computation driven by interactions
• Constructions of polynomially complete quasigroups of arbitrary order
• Format-preserving encryption: a survey
• Quasigroups and their applications
• Applications of quasigroups to cryprography
• Algebraic properties of subquasigroups and construction of finite quasigroups
• Polynomial completeness and completeness of finite n-quasigroups

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)