×

Isomorphism testing of unary algebras. (English) Zbl 0665.68029

The complexity status of the graph-isomorphism problem remains an unsolved open problem in computational complexity theory. It belongs to NP; it is rather unlikely to be NP-complete and also the membership in co-NP is open. Moreover there are natural restrictions of the problem to graphs with a special structure which for rather non-trivial reasons turn out to be polynomially solvable.
It is known that other types of isomorphism testing problems on structures from the world of universal algebra can be shown to be equivalent to the graph isomorphism problem - such problems are called isomorphism complete. The authors have investigated the case for varieties of unary algebras and established a nice characterization: either the isomorphism problem for such a variety is isomorphism complete or it is solvable in polynomial time. The intermediate case which is observed in other algebraic varieties does not occur here.
It can also be shown that one can determine in polynomial time which case is at hand. The authors present a polynomial algorithm which, if given two unary algebras with the same number of operations, either determines that neither of the two algebras belongs to a variety of the special type for which the problem is polynomial time solvable, or if one of the algebras is OK it will determine whether the two are isomorphic or not. The algorithm has a cubic running time.
It should be noted that the varieties which are good are characterized in terms of their algebraic structure: it depends on whether some set of ideals ordered by inclusion gives a linear order or not.
Reviewer: P.van Emde Boas

MSC:

68Q25 Analysis of algorithms and problem complexity
08A60 Unary algebras
PDF BibTeX XML Cite
Full Text: DOI