Djamel Eddine Amir (Mocqua) will defend his thesis, entitled “Computability of Topological Spaces”, on Friday, October 6 at 2pm in room C005.
Abstract:
The main objective of this thesis is to examine the concept of “computable type” and enhance our overall understanding of this notion, as well as provide techniques for verifying or disproving this property. A compact metrizable space is said to have computable type if any semicomputable homeomorphic copy of that space is actually computable. This study builds upon the work of Miller, who demonstrated that finite-dimensional spheres have computable type, and Iljazović and other authors, who extended this property to various spaces, including compact manifolds.
To begin, we establish the equivalence between two distinct definitions of computable type present in the literature, involving metric spaces and Hausdorff spaces, respectively. We contend that the stronger, relativized version of computable type exhibits more favorable properties and lends itself well to topological analysis. Consequently, we derive characterizations of ” strong computable type “ in purely topological terms as well as the descriptive complexity of topological invariants.
It naturally leads to our second objective, is to the study of the expressive power of topological invariants of low descriptive complexity and their ability to differentiate between spaces. Specifically, we investigate two families of low descriptive complexity topological invariants that capture the extensibility and null-homotopy of continuous functions. Using this framework, we revisit previous findings on computable type and discover new insights. Notably, we identify the complexity of the finite topological graph separation problem.
Lastly, our third objective revolves around applying homology theory to study what we term the ” surjection property “ which characterizes the computable type property. For instance, we prove that a finite simplicial complex has (strong) computable type if and only if the star at each vertex satisfies the surjection property. Furthermore, the reduction to homology implies that the computable type property is decidable, for finite simplicial complexes of dimension at most 4.
Jury
PhD Advisors:
- Mathieu HOYRUP, INRIA, Nancy
- Emmanuel JEANDEL, Université de Lorraine, Nancy
Reviewers:
- Olivier BOURNEZ, École Polytechnique, LIX, Paris
- Vasco BRATTKA, University of the Bundeswehr Munich, Germany & University of Cape Town, South Africa
Examiners:
- Nathalie AUBRUN, CNRS, Paris
- Laurent BIENVENU, CNRS, Bordeaux
- Monique TEILLAUD, INRIA, Nancy
Invited members:
- Pierre GUILLON, CNRS, Marseille
