Abstract

In this talk we will review several approaches to study the complexity of classifying effective structures up to isomorphism or another equivalence relation. Calculating the complexity of the set $E_\equiv(K)$ of pairs of indices corresponding to $\equiv$-equivalent computable structures from a fixed class $K$ is one of the approaches. One can use 1-dimensional or 2-dimensional versions of $m$-reducibility to establish the complexity of such index sets. According to this approach, a class is nicely classifiable if the set $E_\equiv(K)$ has hyperarithmetical complexity (provided the class $K$ itself is hyperarithmetical). Another approach is to classify structures on-the-fly. We call a class classifiable in this sense if we can uniquely (up to a fixed equivalence relation) identify each structure from the class after observing a finite piece of the structure.