Logic Seminar- Calculating complexity of the isomorphism problem

Time: Thursday, February 24, 11:00 am-12:00 noon

Place: zoom
https://gwu-edu.zoom.us/j/92062106916

Speaker:  Valentina Harizanov, GWU

Title: Calculating complexity of the isomorphism problem

Abstract: We will continue to investigate the complexity of the isomorphism problem for computable members in various classes of structures. The sharpness of such results is established by proving completeness in some complexity classes via computable reductions. We will present results on calculating the complexity of the computable isomorphism problem, illustrating great diversity among various kinds of structures. We will discuss how these complexity results allow us to distinguish between classifiable and non-classifiable classes of structures.