A classification problem in mathematics is the problem of determining when two of a given collection of structures are appropriately equivalent. A solution of a classification problem involves providing some manner for making the determination of equivalence, such as developing a complete system of invariants. The difficulty of a classification problem can be measured by considering how complicated such invariants must be. Using descriptive set theory, we can provide a precise notion of when one classification problem is fundamentally more complicated than another, and provide a number of standard benchmarks for levels of complexity. In this talk, I will first give an overview of this theory of Borel reducibility of equivalence relations and classification problems. I will then apply this theory to determine the complexity of the isomorphism problem for subshifts, i.e., the dynamical systems corresponding to topologically closed and shift-invariant subsets of the space of all bi-infinite sequences on a finite alphabet, considered up to shift-preserving topological isomorphism.
Thinking about UNT?
It's easy to apply online. Join us and discover why we're the choice of over 46,000 students.
Apply now