Verifying nonrigidity
type: Item
instance of: scholarly article
title: Verifying nonrigidity
zbMATH Open document ID: 0587.68042
DOI: 10.1016/0020-0190(86)90147-X
author: Pavel Goralčík
author: Václav Koubek
published in: Information Processing Letters
publication date: 1986-01-01T00:00:00Z
review text: An algebra is called rigid if it has no other endomorphism than identity. We prove that the problem whether a finite algebra A is nonrigid is NP- complete as soon as the type of A has either one binary or two unary symbols. The apparently harder problem whether \(| End A| >k\), for a given integer \(k\geq 1\), can be reduced to the nonrigidity problem and thereby is NP-complete. By contrast, the endomorphisms of a mono-unary algebra can be counted in polynomial time.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 08A60
Mathematics Subject Classification ID: 08A35
zbMATH DE Number: 3943027
zbMATH Keywords: nonrigid algebra
zbMATH Keywords: NP-completeness
zbMATH Keywords: endomorphism
zbMATH Keywords: finite algebra
zbMATH Keywords: mono- unary algebra
MaRDI profile type: Publication
cites work: Q4773298
cites work: The Complexity of Near-Optimal Graph Coloring
cites work: Graphs and k-Societies
cites work: Q4142699
cites work: On a technique for representing semigroups as endomorphism semigroups of graphs with given properties
cites work: Über Abbildungen von Mengen
cites work: Q3208855
cites work: Fast multiplication of large numbers
full work available at URL: 0020-0190(86)90147-x
OpenAlex ID: W2912005352
description: scientific article; zbMATH DE number 3943027