Checking quasi-identities in a finite semigroup may be computationally hard.
type: Item
instance of: scholarly article
title: Checking quasi-identities in a finite semigroup may be computationally hard.
zbMATH Open document ID: 1076.20043
author: M. V. Volkov
published in: Studia Logica
publication date: 2005-04-07T00:00:00Z
review text: Many basic questions in algebra turn out to be (computationally) surprisingly difficult. For instance, it was shown by \textit{C. Bergman} and \textit{G. Slutzki} [SIAM J. Comput. 30, No. 2, 359-382 (2000; Zbl 0963.68077)] that the question of whether two finite algebras satisfy the same quasi-identities is NP-complete. This paper considers the question of whether a fixed finite algebra satisfies a given identity. This clearly belongs to co-NP, and in this paper a 10 element semigroup for which the question is co-NP complete is constructed. This is not the smallest possible such semigroup, but it is of interest because the checking of identities in it can be done in low polynomial time.
reviewed by: Sheila Oates-Williams
Mathematics Subject Classification ID: 20M07
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 08C15
zbMATH DE Number: 2153450
zbMATH Keywords: finite semigroups
zbMATH Keywords: identities
zbMATH Keywords: quasi-identities
zbMATH Keywords: NP-completeness
MaRDI profile type: Publication
full work available at URL: s11225-005-0356-5
OpenAlex ID: W2005496785
cites work: Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
cites work: Q3848243
cites work: Q4198056
cites work: Complexity issues of checking identities in finite monoids
cites work: Q3291034
cites work: Q4298260
cites work: THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
DOI: 10.1007/S11225-005-0356-5
description: scientific article; zbMATH DE number 2153450