[PhD Mocqua] Computability of subsets of topological spaces

Supervision: Emmanuel Jeandel (emmanuel.jeandel@loria.fr) and Mathieu Hoyrup (mathieu.hoyrup@inria.fr), in the Inria team-project Mocqua.

Topic: computability theory.

Keywords: computability, complexity, topology.

Required background: basics in theoretical computer science, knowledge in topology welcome.


Computability theory is the study of the theoretical possibility of computing various mathematical objects with arbitrary precision. Computability of subsets of the plane is a particularly important topic, because it is the study of the existence of a program that draws the set on a screen with arbitrary resolution. For instance, whether the famous Mandelbrot set is computable is still an open problem related to a conjecture in complex analysis. However, the definition of the Mandelbrot set immedtialy translates into an algorithm running in infinite time and progressively coloring the points outside the set, with no guarantee on the time the picture is complete. We say that the set is semi-computable. This example illustrates the fact that computability interacts closely with mathematical analysis.

PhD project

In this PhD project, we propose to investigate the relationship between the notions of computability of a set and its topological or geometrical properties. It has been shown for instance by Miller in [M02] that for any set that is homeomorphic to a finite-dimensional sphere, semi-computability and computability are actually equivalent. Several extensions of this result have been studied by Iljazovic and his co-authors, in [IS18] for instance. We propose to carry out a complete investigation of these questions, trying to characterize the classes of sets for which semi-computability is equivalent to computability, identifying the topological and geometrical properties making this equivalence possible.

In addition to computability, one can investigate complexity of sets. There exists several notions of complexity for a set, a priori equivalent (under usual complexity assumptions such as P≠NP). We propose to investigate the influence of topological and geometrical properties of a set on the relationship between different notions of complexity. For instance, we expect the result that several complexity notions coincide for convex sets.

The whole study lies at the intersection between theoretical computer science (computability and complexity theory) and mathematical analysis, in particular topology and geometry.

[IS18] Zvonko Iljazovic, Igor Susic: Semicomputable manifolds in computable topological spaces. J. Complex. 45: 83-114 (2018)
[M02] Joseph S. Miller: Effectiveness for Embedded Spheres and Balls. Electron. Notes Theor. Comput. Sci. 66(1): 127-138 (2002)

Logo d'Inria