An assertion concerning functionally complete algebras and NP-completeness
type: Item
instance of: scholarly article
title: An assertion concerning functionally complete algebras and NP-completeness
zbMATH Open document ID: 1153.68020
author: Gábor Horváth
author: Chrystopher L. Nehaniv
author: Csaba Szabó
published in: Theoretical Computer Science
publication date: 2008-11-18T00:00:00Z
full work available at URL: http://hdl.handle.net/2437/114142
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 08A70
zbMATH DE Number: 5368363
zbMATH Keywords: functionally complete algebras
zbMATH Keywords: identity checking
zbMATH Keywords: solvability of equations
zbMATH Keywords: solvability of systems of equations
zbMATH Keywords: NP-completeness
zbMATH Keywords: coNP-completeness
MaRDI profile type: Publication
OpenAlex ID: W2061999747
cites work: The equivalence problem for finite rings
cites work: Results on the equivalence problem for finite groups.
cites work: Q4198056
cites work: The complexity of the equivalence problem for nonsolvable groups
cites work: THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
cites work: The complexity of equivalence for commutative rings
cites work: COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
cites work: TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
cites work: Unification in primal algebras, their powers and their varieties
cites work: Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
cites work: MONOIDS AND COMPUTATIONS
DOI: 10.1016/J.TCS.2008.08.028
description: scientific article; zbMATH DE number 5368363