Classification problem for effective structures

SASW09 - International conference on computability, complexity and randomness

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.

This talk is part of the Isaac Newton Institute Seminar Series series.