A Weihrauch Degree Perspective on the Difficulty of Finding Isomorphisms

Explore the computational complexity of finding isomorphisms between mathematical structures through the lens of Weihrauch degrees in this 49-minute conference talk. Delve into computable model theory by examining how difficult it is to construct isomorphisms between two given structures, building upon established concepts like computably categorical structures and degrees of categoricity. Learn about the newly defined cat(M) problem, which takes pairs of isomorphic copies of a countable structure M as instances and requires isomorphisms between them as solutions. Discover the relationship between a structure's degree of categoricity and its Weihrauch degree, including how uniformly computably categorical structures correspond to the identity degree id, while some computably categorical structures rank strictly above id in the Weihrauch hierarchy. Investigate the general categoricity problem that considers pairs of isomorphic structures without restriction to a particular base structure, and understand its equivalence to choice on Baire space. Gain insights into how uniformity plays a crucial role in distinguishing between different levels of computational difficulty in finding structural isomorphisms.