Alexandre Razborov

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Alexandre Alexandrovitch Razborov (russe : Алекса́ндр Алекса́ндрович Разбо́ров, né le 16 février 1963), connu aussi sous le nom de Sacha Razborov, est un mathématicien et un informaticien théoricien soviétique et russe. Il est le lauréat du prix Nevanlinna en 1990 pour son travail sur la théorie de la complexité[1], et en 2007 du prix Gödel avec Steven Rudich (en) pour leur article « Natural proofs (en) »[2].

Biographie[modifier | modifier le code]

Son directeur de thèse est Sergueï Adian (en). Il est élu le 26 mai 2000 membre correspondant de l'Académie des sciences de Russie[3]. Son nombre d'Erdős est 2[4].

Razborov devient en 2009 Andrew MacLeish (en) Distinguished Service Professor au département informatique de l'université de Chicago.

Travaux[modifier | modifier le code]

Son travail le plus connu, en collaboration avec Steven Rudich, est l'introduction de la notion de natural proofs, une classe de stratégies permettant de prouver des bornes inférieures dans la théorie de la complexité des algorithmes. En particulier Razborov et Rudich ont montré que sous l'hypothèse que certaines fonctions à sens unique existent, de telles preuves ne permettent pas de résoudre le problème P = NP, qui nécessiterait alors de nouvelles techniques.

Bibliographie[modifier | modifier le code]

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Alexander Razborov » (voir la liste des auteurs)

  1. (en) « International Mathematical Union: Rolf Nevanlinna Prize Winners »
  2. (en) « EATCS: Gödel Prize - 2007 »
  3. (en) « Russian Academy of Sciences: Razborov Aleksandr Aleksandrovich: General info: History »
  4. (en) « Some Famous People with Finite Erdös Numbers : Nevanlinna Prize winners »

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]