Verifying nonrigidity (Q1072373): Difference between revisions

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.