Alexandru Razborov

Alexandru Razborov Date esentiale
Naștere 16 februarie 1963
Acasă Drapelul Statelor Unite Statele Unite
Naţionalitate Rusia
Zone Informatică teoretică , matematică
Instituții Institutul Matematic Steklov , Universitatea din Chicago , Institutul Tehnologic Toyota din Chicago  (ro)
Diplomă Universitatea de Stat din Moscova
Renumit pentru teoria grupurilor , informatică teoretică
Premii Premiul Nevanlinna (1990)
Premiul Gödel (2007)

Alexandru Alexandrovici Razborov ( rusă  : Алекса́ндр Алекса́ндрович Разбо́ров , născut pe16 februarie 1963), cunoscut și sub numele de Sacha Razborov , este un matematician și teoretician informatic sovietic și rus . A câștigat Premiul Nevanlinna în 1990 pentru munca sa privind teoria complexității , iar în 2007 Premiul Gödel cu Steven Rudich pentru articolul lor „  Dovezi naturale  ” .

Biografie

Conducătorul tezei sale este Serghei Adian . Razborov a devenit în 2009 Andrew MacLeish  (ro) profesor de serviciu distins în departamentul IT al Universității din Chicago .

Premii și recunoaștere

El este ales pe 26 mai 2000membru corespondent al Academiei de Științe din Rusia . Numărul său Erdős este 2. În 2010 a fost lector Gödel cu o prelegere intitulată Complexitatea dovezilor propoziționale . În 2013, a primit Premiul Robbins pentru articolul său „Despre densitatea minimă a triunghiurilor în grafice”.

Lucrări

Cea mai cunoscută lucrare a sa, în colaborare cu Steven Rudich, este introducerea conceptului de dovezi naturale ( dovezi naturale ), o clasă de strategii pentru a dovedi limite inferioare în teoria complexității algoritmilor . În special Razborov și Rudich au arătat că, sub ipoteza că există unele funcții unidirecționale , astfel de dovezi nu permit rezolvarea problemei P = NP , care ar necesita apoi noi tehnici.

Bibliografie

Note și referințe

(fr) Acest articol este preluat parțial sau în întregime din articolul din Wikipedia engleză intitulat „  Alexander Razborov  ” ( vezi lista autorilor ) .
  1. (în) „  Câștigătorii Premiului Rolf Nevanlinna pentru Uniunea Internațională de Matematică  ” [ arhivă27 decembrie 2008] (accesat la 20 ianuarie 2014 )
  2. (în) „  EATCS: Premiul Gödel - 2007  ”
  3. (în) „  Alexander Razborov  ” pe site-ul Mathematics Genealogia Project
  4. (în) „  Academia Rusă de Științe: Razborov Aleksandr Aleksandrovich: Informații generale: Istorie  ”
  5. (în) „  Unii oameni celebri cu numere finite de erdos: câștigători ai premiului Nevanlinna  ”
  6. Razborov: Despre densitatea minimă a triunghiurilor din grafice , Combinatorică, Probabilitate și Calcul } 17 (4): 603-618, 2008.

Vezi și tu

Articole similare

linkuri externe