Isomorphism Testing of Unary Algebras

Two problems are said to be polynomially equivalent if each is polynomially reducible to the other. A problem is said to be isomorphism-complete if it is polynomially equivalent to the graph isomorphism problem. We prove that the isomorphism problem in any variety of unary algebras is either isomorphism-complete, or solvable in polynomial time. We formulate a condition C under which the isomorphism problem in a variety V of unary algebras can be solved in polynomial time. We present an algorithm that can be applied to any pair of unary algebras with the same number of operations and decides whether the algebras are isomorphic or not in $O(n^3 )$ time, provided one of them belongs to a variety satisfying C. The validity of the last condition is tested by the algorithm in linear time.