Subhash Khot, prix Nevanlinna 2014

Le prix Rolf Nevanlinna est remis une fois tous les quatre ans lors du Congrès international des mathématiciens.
Il récompense des travaux qui ont trait aux aspects mathématiques de l’informatique.

Le prix 2014 est remis à Subhash Khot, 36 ans, professeur à l’Institut Courant de l’Université de New York.
Licence à l’Indian Institute of Technology de Bombay, puis doctorat à l’Université de Princeton en 2003.
Il a reçu en 2010 le prix Waterman, très prestigieux également comme on le voit en consultant la liste des lauréats (il faut avoir moins de 35 ans et être de nationalité américaine ou résident aux USA).

Il est intéressant de constater que le prix n’est pas remis à cause d’un théorème ou d’un résultat mais pour une conjecture. On minimise souvent le rôle des conjectures en mathématiques, en informatique théorique en l’occurrence. La conjecture la plus importante dans la théorie de la complexité résiste aux spécialistes depuis 40 ans : c’est l’un des fameux problèmes à un million de dollars de l’institut Clay, la question de montrer que \(P \neq NP\).
En 1903, F.N. Cole donnait une conférence intitulée « Sur la factorisation des grands nombres ».
Sans un mot, il écrivit au tableau :
\[2^{67}-1 = 147573952589676412927 = 193707721 \times 761838257287, \]
et il commença à démontrer son « théorème » en posant la multiplication et en vérifiant à la main qu’en effet cette égalité est bien valide.
Il illustrait ainsi qu’il est bien plus facile de vérifier qu’une preuve est correcte que de la découvrir.
Combien de temps avait-il fallu à F.N. Cole pour factoriser \(2^{67}-1\) ?
Selon lui, cela lui avait pris tous ses dimanches pendant trois ans !
La conjecture \(P \neq NP\) consiste à {démontrer} qu’en effet il existe des problèmes pour lesquels il est difficile de trouver une solution mais pour lesquels il est facile de vérifier une solution qu’on vous présente.
Un exemple élémentaire est le suivant.
Considérez un graphe fini, c’est-à-dire un ensemble de \(n\) points, appelés les sommets, et d’un certain nombre de liens, appelés arêtes, qui joignent certains de ces points.

Demandez-vous, ou demandez à un ordinateur, s’il est possible de colorier les sommets en trois couleurs, disons bleu, blanc et rouge, en imposant que deux sommets reliés par une arête aient des couleurs différentes ?
On peut bien sûr tester une à une toutes les possibilités de coloration, il y en a \(3^n\), et vérifier si elles vérifient la contrainte imposée ?
Le problème est que \(3^n\) peut-être très grand et un même un ordinateur ne peut pas gérer cela en un temps raisonnable.
Prenez par exemple \(n=100\) et supposez que votre ordinateur traite \(10^{10}\) cas par seconde…
Il devra travailler pendant \(3^{100}10^{-10}\) secondes, ce qui est très largement supérieur à l’âge de l’univers !
Peut-on trouver une méthode qui permette d’aller plus vite ?
Il s’agirait d’une méthode dont le temps de calcul serait plus petit qu’une puissance de \(n\) plutôt qu’une exponentielle ?
Voilà le problème \(P \neq NP\) sur lequel les théoriciens buttent depuis 40 ans.
Notez encore que si je vous donne des couleurs sur les sommets, il vous sera facile, en très peu de temps, de vérifier si la solution que je vous propose est correcte.
Il semble bien que presque tous les théoriciens sont convaincus qu’il existe en effet des problèmes pour lesquels il est difficile de trouver une solution et facile de vérifier une solution qu’on vous propose.

La conjecture de Khot s’appelle la « {unique games conjecture} » pour des raisons un peu obscures (pour moi en tous cas) et date de 2002.
La première chose qu’il faut dire est que cette conjecture n’a de sens que si \(P \neq NP\).
Il s’agit cette fois de la complexité de problèmes dans lesquels on ne cherche pas à savoir si quelque chose est vrai ou faux (coloriable ou pas, par exemple) mais dans lesquels on cherche à optimiser une certaine quantité.
Voici un exemple.
On part d’un graphe fini, comme précédemment, et on cherche à déterminer une partie \(E\) de l’ensemble des sommets qui soit telle que tout sommet est relié à au moins un élément de \(E\).
Bien entendu, on cherche des parties \(E\) qui contiennent le moins d’élément possible.
Il se trouve qu’il est difficile de trouver une telle partie minimale.
En revanche, si on est moins ambitieux, on peut trouver facilement des parties \(E\) qui certes ne sont pas optimales mais dont le nombre d’éléments est au plus deux fois cet optimum (qui est difficile à déterminer).
Partez d’une arête de votre choix et mettez ses deux extrémités dans votre ensemble \(E\).
Supprimez de votre graphe cette arête ainsi que toutes les arêtes qui aboutissent à l’un de ses deux sommets.
Recommencez avec ce qui reste.
A la fin, quand il ne reste plus aucun sommet, vous avez obtenu une partie \(E\) et il est clair que tout sommet est en effet connecté à l’un des éléments de \(E\).
Le nombre d’étapes de votre recherche est plus petit que la moitié du nombre de sommets.
Il est facile de voir par ailleurs que le nombre d’éléments de \(E\) est au plus deux fois l’optimum.
Voilà donc un problème dans lequel la solution optimale semble difficile mais dont une solution approchée est facile à obtenir.
Approché à un facteur 2 près…
Peut-on faire mieux, et trouver facilement un ensemble optimal à 1% près par exemple ?
C’est ici que la conjecture des « unique games » entre en jeu.
Elle permet dans de nombreux cas de donner une limite.
Dans notre exemple, en utilisant le [théorème PCP->755], qui avait été discuté au congrès précédent, Dinur et Safra ont montré qu’il n’existe pas d’algorithme rapide pour trouver une solution approchée avec un facteur meilleur que \(10 \sqrt{5}-21 \simeq 1,36\).
En 2003, Khot et Regev ont montré que si la conjecture « unique games » était vraie, il en résulterait qu’on ne peut pas faire mieux que le facteur 2.
C’était l’une des premières indications de l’importance de cette conjecture.

Citation : Subhash Khot reçoit le prix Nevanlinna pour sa définition visionnaire du problème « unique games » et son rôle de leader dans les efforts pour comprendre sa complexité, et son rôle central dans l’étude de problèmes d’approximation efficaces, qui ont produit des avancées majeures dans la conception d’algorithmes et dans la question de la difficulté de l’approximation, et de nouvelles interactions entre la complexité des calculs, l’analyse et la géométrie. ¹Subhash Khot is awarded the Nevanlinna prize for his prescient definition of the “Unique Games” problem, and his leadership in the effort to understand its complexity and its pivotal role in the study of efficient approximation of optimization problems, have produced breakthroughs in algorithmic design and approximation hardness, and new exciting interactions between computational complexity, analysis and geometry.

Deux articles intéressants… Subhash Khot : On the unique games conjectures, un article de présentation, pas si facile…Erica Klarreich, Approximately hard, superbe article de vulgarisation.