Complexity of the isomorphism problem

For certain classes of algebraic structures, closed under isomorphism, we investigate computability-theoretic complexity of the isomorphism problem for its computable members. More precisely, the computable isomorphism problem for a class K of structures, is the set of pairs of computable indices (algorithmic codes) for computable structures in K, which are isomorphic. The exact complexity is measured using the notions of reducibility of problems and of their completness. For some classes of structures, the computable isomorphism problem is complete at various levels of arithmetical hierarchy, such as for vector spaces over a fixed infinite computable field, algebraically closed fields of a fixed characteristic, or equivalence structures. On the other hand, there are classes of structures with Sigma _{1}^{1}-complete computable isomorphism problem, which is of maximal complexity. These classes include abelian p-groups, trees, linear orders, distributive lattices, and 2-step nilpotent groups. They have isomorphic computable structures that are not hyperarithmetically isomorphic. One of the methods we use to establish such results is based on uniform effective interpretations of computable binary relations into computable structures from the corresponding classes.