University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Classification problem for effective structures

Classification problem for effective structures

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact nobody.

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2022 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity