Classification problem for effective structures

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

• Ekaterina Fokina (Vienna University of Technology)
• Thursday 09 June 2022, 13:30-14:30
• Seminar Room 1, Newton Institute.

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.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.