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

Title:Measuring Complexity in Computable Structure Theory
Speaker:  Valentina Harizanov, GWU
Date and Time:  Friday, February 22, 12:00-1:00PM
Place: Rome Hall (801 22nd Street), Room 771

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.