University Seminar: Logic Across Disciplines- Measuring Complexity in Computable Structure Theory 

Abstract:  In order to measure complexity of problems in computable structure theory, one of the main strategies is to find an optimal description of the class of structures under investigation. This often requires the use of various algebraic properties of the structures. To prove the sharpness of our description, we use the notion of many-one completeness. The complexity is often expressed using hyper-arithmetical sets or their differences. As examples of different complexity problems we will present some recent results.