Spécialité : IInformatique
Laboratoire : LIPN
Directeurs de thèse : Damiano Mazza et Jean-Baptiste Joinet
Une approche catégorique à la complexité descriptive
La complexité algorithmique est un sujet central de l’informatique théorique depuis les années 60 mais en dépit des efforts de la communauté il reste de nombreuses questions ouvertes.
Ce constat encourage la recherche d’approches alternatives de la discipline afin d’enrichir notre compréhension de la notion de complexité algorithmique, et ceci autant du point de vue de l’informatique que de la philosophie de l’informatique car le concept même de complexité computationnelle reste assez vaguement défini de manière générale.
Une de ces approches alternatives est la complexité descriptive, il s’agit de définir la complexité d’une tâche informatique non pas par les ressources nécessaires à sa résolution mais par l’expressivité du langage logique nécessaire pour la décrire.
Ce projet prend place dans un contexte où de nombreux nouveaux outils ont été développé pour étudier la logique mais qui n’ont pas encore été utilisé avec la complexité descriptive.