KHOT SUBHASH (1978- )

Carte mentale

Élargissez votre recherche dans Universalis

Le mathématicien indien Subhash Khot est un théoricien de l’informatique, spécialiste des problèmes d’optimisation dans ce qu’il est convenu d’appeler la théorie de la complexité. Né le 10 juin 1978 à Ichalkaranji, ville moyenne de l’État du Maharashtra dans l’ouest de l’Inde, Khot est le fils de deux médecins. Classé premier au concours d’entrée de l’Institut indien de technologie (I.T.T.) de Bombay en 1995, il y obtient sa licence en informatique en 1999 et s’installe aux États-Unis pour ses études de doctorat qu’il accomplit sous la direction du professeur Sanjeev Arora (né en 1968) à l’université de Princeton. Son travail sur « des techniques nouvelles appliquées à la vérification statistique de preuves et de résultats d’inapproximation » est immédiatement reconnu comme extrêmement novateur. Après sa thèse soutenue en 2003, il enseigne à l’Institut de technologie de Géorgie (Georgia Tech) à Atlanta (Géorgie, États-Unis), avant de rejoindre l’université de New York où il est professeur à l’Institut Courant de sciences mathématiques depuis 2007.

C’est pendant ses années de doctorant, en 2002, que Khot énonce la conjecture des jeux uniques (U.G.C. pour unique games conjecture). Selon cette conjecture, pour une certaine classe de problèmes (appelés jeux uniques), il est NP-difficile de décider si l'on peut trouver une solution proche de l'optimale, ou si toutes les solutions sont loin de l'optimale. En théorie de la complexité, NP désigne les problèmes solubles en temps polynomiaux sur une machine de Turing non déterministe. Dire qu’un problème est NP-difficile signifie qu’il est au moins aussi difficile que tout problème NP connu. Cette conjecture généralise le théorème P.C.P. (probabilistically checkable proof, « preuve vérifiable de façon statistique »), établi en 1990-1992, qui affirme que tout problème de décision appartenant à la classe NP a une preuve qui peut être vérifiée par un algorithme contenant des tirages aléatoires. Autrement dit, il suffit de lire un nomb [...]


1  2  3  4  5
pour nos abonnés,
l’article se compose de 2 pages


Écrit par :

  • : directeur de recherche au CNRS, centre de physique théorique de l'École polytechnique, Palaiseau

Classification

Pour citer l’article

Bernard PIRE, « KHOT SUBHASH (1978- ) », Encyclopædia Universalis [en ligne], consulté le 22 novembre 2019. URL : http://www.universalis.fr/encyclopedie/subhash-khot/