Verifying nonrigidity (Q1072373)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Verifying nonrigidity |
scientific article; zbMATH DE number 3943027
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Verifying nonrigidity |
scientific article; zbMATH DE number 3943027 |
Statements
Verifying nonrigidity (English)
0 references
1986
0 references
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.
0 references
nonrigid algebra
0 references
NP-completeness
0 references
endomorphism
0 references
finite algebra
0 references
mono- unary algebra
0 references
0 references
