Actualités

Un énorme progrès sur la complexité et les graphes ?

Le 5 novembre 2015

Timothy Gowers, mathématicien anglais lauréat de la médaille Fields en 1998 (ce qui sera pris a minima dans ce billet comme un gage de sérieux...), retransmet une rumeur croissante sur son blog : László Babai, informaticien théoricien lauréat du prix Gödel (idem...) s’apprêterait à révéler un algorithme quasi-polynomial pour décider si deux graphes sont isomorphes, ce qui pourrait être le résultat de la décennie en informatique théorique !

D’abord, le côté people : la rumeur se fonde sur le titre d’un exposé que Babai va donner à l’université de Chicago (la sienne) la semaine prochaine, mardi 10 :

Laszlo Babai (University of Chicago) : Graph Isomorphism in Quasipolynomial Time (Combinatorics and TCS seminar)

Date Mar., 10 novembre, 15:00 – 16:00

We outline an algorithm that solves the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (SI) and Coset Intersection (CI) in quasipolynomial ($\exp(\mathrm{polylog} n)$) time.

The best previous bound for GI was $\exp(\sqrt{n \ln n})$, where $n$ is the number of vertices (Luks, 1983). For SI and CI the best previous bound was similar, $\exp(\sqrt{n}(\ln n)^c)$, where $n$ is the size of the permutation domain (the speaker, 1983).

(Nous esquissons un algorithme qui résout le problème de l’isomorphisme de graphes (GI) et les problèmes associés de l’isomorphisme de chaînes (SI) et de l’intersection de classes (CI) en temps quasi-polynomial ($\exp(\mathrm{polylog} n)$).

La meilleure borne connue auparavant pour GI était $\exp(\sqrt{n \ln n})$, où $n$ est le nombre de sommets (Luks, 1983). Pour SI et CI, la meilleure borne connue était semblable, $\exp(\sqrt{n}(\ln n)^c)$, où $n$ est la taille du domaine de la permutation (l’orateur, 1983).)

Un des grands problèmes des mathématiques est de décider si P=NP. En informatique théorique, le problème de l’isomorphisme de graphes est presque aussi recherché. Les graphes sont une structure combinatoire dépouillée mais omniprésente en informatique et en mathématiques : un graphe est la donnée d’un ensemble de sommets (dont la nature n’importe pas) et d’arêtes qui relient certains sommets deux par deux. On dit que deux graphes sont isomorphes si on peut faire se correspondre les sommets de l’un avec ceux de l’autre de sorte à envoyer les arêtes de l’un sur les arêtes de l’autre ; autrement dit, à un ré-étiquetage des sommets près, les deux graphes sont indiscernables.

Étant donnés deux graphes, c’est un problème important de décider s’ils sont isomorphes ou pas, aussi bien pour la théorie que pour la pratique (cela a des répercussions sur la vitesse de consultation des bases de données relationnelles où sont stockées les informations de très nombreux sites, dont celui-ci). Vérifier que deux graphes sont isomorphes quand on a un candidat pour l’isomorphisme est un problème algorithmiquement « facile » (plus précisément, il se résout en temps polynomial ; on dit que le problème est dans la classe NP). La question est de savoir si l’on peut trouver un isomorphisme efficacement (en temps polynomial). L’algorithme de Babai donnerait une façon « assez efficace » (en temps quasi-polynomial, c’est-à-dire borné par $\exp\bigl(A(\ln n)^c\bigr)$ où $A$ et $c$ sont des constantes et $n$ est la taille du graphe ; pour $c=1$ on retrouve le temps polynomial).

En savoir plus : le blog de Timothy Gowers

Partager cette actualité

La tribune des mathématiciens

Suivre IDM