Seminar
| Parent Program: | |
|---|---|
| Location: | SLMath: Online/Virtual |
Hilbert’s Tenth Problem was the only decision problem among his twenty-three problems. Precise mathematical theory of (in)computability and its interaction with number theory led to the negative solution of the problem. The seminar will focus on modern topics on computability-theoretic phenomena in number-theoretic and other algebraic and model-theoretic structures.
To participate in this seminar, please register here: https://www.msri.org/seminars/25206
Degree Spectra Of Analytic Complete Equivalence Relations
To participate in this seminar, please register here: https://www.msri.org/seminars/25206
Abstract: We present new results on the complexity of the classification problem of countable structures and their computational complexity. We show that the elementary bi-embeddability relation on the class of graphs is analytic complete under Borel reducibility by giving a reduction from the bi-embeddability relation on graphs. We then compare the degree spectra with respect to these equivalence relations. The degree spectrum of a countable structure with respect to an equivalence relation E is the set of Turing degrees of structures E-equivalent to it. We show that the degree spectra of structures with respect to bi-embeddability and elementary bi-embeddability are related: Every bi-embeddability spectrum of a graph is the set of jumps of Turing degrees in the elementary bi-embeddability spectrum of a graph.
 |
Slides
|
Degree Spectra Of Analytic Complete Equivalence Relations
| H.264 Video | 25197_28695_8670_Degree_Spectra_of_Analytic_Complete_Equivalence_Relations.mp4 |