[Thèse Mocqua] Calculabilité des ensembles dans les espaces topologiques

Encadrement : Emmanuel Jeandel (emmanuel.jeandel@loria.fr) et Mathieu Hoyrup (mathieu.hoyrup@inria.fr) de l’équipe-projet Inria Mocqua.

Domaine : théorie de la calculabilité.

Mots-clés : calculabilité, complexité, topologie

Pré-requis : bases en informatique théorique, connaissances en topologie bienvenues.

Contexte

La théorie de la calculabilité permet d’étudier la possibilité théorique de calculer à précision arbitraire des objets mathématiques de toutes sortes. La calculabilité d’ensembles du plan est un thème particulièrement important, car elle revient à savoir s’il existe un programme qui dessine l’ensemble sur un écran de résolution arbitraire. La calculabilité de l’ensemble de Mandelbrot est par exemple un problème ouvert, lié à une conjecture en analyse complexe. En revanche, la définition même de cet ensemble fournit un algorithme dont l’exécution est potentiellement infinie, colorant petit à petit les points extérieurs à l’ensemble, sans garantie sur le temps au bout duquel tous ces points ont été colorés. On dit alors que l’ensemble est semi-calculable. Cet exemple illustre le fait que les questions de calculabilités interagissent fortement avec l’analyse mathématique.

Projet de thèse

Dans ce projet de thèse, nous proposons d’étudier les liens entre calculabilité d’un ensemble et ses propriétés topologiques ou géométriques. Il a par exemple été montré dans [M02] que pour tout ensemble homéomorphe à une sphère de dimension finie, la semi-calculabilité est équivalente à la calculabilité. Plusieurs extensions de ce résultat ont été étudiées par Iljazovic et ses co-auteurs, dans [IS18] par exemple. Nous proposons une étude plus approfondie de ces questions, en cherchant à caractériser les classes d’ensemble pour lesquels la semi-calculabilité implique la calculabilité, en identifier les propriétés topologiques ou géométriques qui permettent ce type de résultat.

Outre la calculabilité, il est aussi possible de définir la complexité d’un ensemble (du plan, par exemple). Il existe plusieurs notions de complexité d’un ensemble, en général différentes (sous des hypothèses de complexité du type P≠NP). Nous proposons d’étudier l’influence des propriétés topologiques et géométriques d’un ensemble sur les liens entre ces notions de complexités. Un résultat que l’on peut espérer est par exemple la coïncidence de plusieurs notions de complexité pour les ensembles convexes.

L’étude se situe à l’intersection de l’informatique théorique (théories de la calculabilité et de la complexité) et de l’analyse mathématique, en particulier topologie et géométrie.

[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