UREM-ULB :
Unité de Recherche sur l’Enseignement des Mathématiques

ERC:un nouveau grant en mathématique

Samuel Fiorini décroche un consolidator grant du Conseil européen de la recherche (ERC) pour une recherche mêlant algorithmes et géométrie.

Imaginez que vous deviez vous rendre d’un point A à un point
B, quel chemin le plus court ou le plus rapide emprunter ? Rien
de plus facile, votre GPS va le calculer, pensez-vous ? Et vous
avez raison : n’importe quel GPS pourra vous fournir la réponse
rapidement. Mais imaginez maintenant que vous alliez non
pas de A à B, mais de A à Z, en passant entre autres par D, G ou
encore L, selon un ordre à définir, le tout en évitant les pertes de
temps et retours sur ses pas, tout en devant gérer des livraisons
périssables et une météo instable... Là, le problème devient
complexe, voire trop complexe : dès que le nombre de points
dépasse les cent mille, nous sommes incapables d’en trouver
une solution optimale aujourd’hui tant la puissance de calcul et
le temps nécessaire sont considérables.

Chargé de cours au Département de mathématique en Faculté
des Sciences, Samuel Fiorini s’intéresse à la théorie de la
complexité, qui se situe à l’interface entre mathématique
et informatique. La question phare de cette théorie est la
question P versus NP. Le Clay Mathematics Institute offre une
prime d’1 million de dollars pour sa résolution ! Les problèmes
dans P – par exemple trouver un plus court chemin entre un
point A et un point B dans un réseau routier – peuvent être
résolus rapidement. Autrement dit, il existe pour chacun de
ces problèmes, un algorithme efficace. En revanche, il existe
beaucoup de problèmes dans NP pour lesquels on ne connaît
pas de tels algorithmes ; ces problèmes semblent nécessiter un
temps de calcul croissant très rapidement. Par définition, tous
les problèmes dans P sont en particulier dans NP. La question
P versus NP est de démontrer mathématiquement que tous les
problèmes dans NP sont également dans P, ou au contraire que
P et NP sont différents, ce qui signifierait que pour une large part
des problèmes, tout algorithme doit d’une manière ou d’une
autre recourir à la recherche exhaustive pour trouver une solution
optimale, résultant en un temps de calcul prohibitif.

Grace au soutien du Conseil européen de la recherche (ERC),
Samuel Fiorini va mettre en place une équipe – 2 doctorants, 3
post-docs seront engagés à partir d’octobre 2014 – au sein du
service de Géométrie, Combinatoire et Théorie des groupes pour
étudier la théorie de la complexité par un biais géométrique.
« J’ai abordé ces problèmes dans un article, co-écrit notamment
avec Serge Massar du service OPERA puisqu’il existe des liens
étroits avec la physique quantique. L’article a été reconnu
meilleur article du Symposium on Theory of Computing (STOC)
en 2012 et a suscité beaucoup de discussions sur des blogs
scientifiques » explique Samuel Fiorini, « Mon projet ERC
vise à mieux comprendre une méthodologie puissante et
très utilisée consistant à reformuler un problème complexe
de manière géométrique, avec autant de dimensions qu’il y
a de variables. On obtient alors un objet mathématique, un
polytope (généralisation des polygones et polyèdres que l’on
connaît en 2D et 3D). Chaque sommet du polytope correspond
à une solution du problème ; nous cherchons un point d’hauteur
maximum dans une certaine direction qui donnera la meilleure
solution. En étudiant la complexité de ces polytopes, j’espère
mieux cerner la complexité des problèmes correspondants et
réussir à les catégoriser en problèmes solubles ou insolubles
par cette méthodologie géométrique ».

Nathalie Gobbe

Source : Esprit libre Jan. – Fév. – Mars 2014 – n° 31 p. 18