Alexandru Razborov
Alexandru Razborov
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
- (ro) „ Limite inferioare pentru complexitatea monotonă a unor funcții booleene ” , Doklady Akademii Nauk SSSR , vol. 31,1985, p. 354–357 ( citiți online [ pdf ])
- (ro) „ Limite inferioare ale complexității monotone a permanentului logic ” , Note matematice ale Academiei de Științe ale URSS , vol. 37, nr . 6,Iunie 1985, p. 485–493 ( DOI 10.1007 / BF01157687 )
-
(ru) О системах уравнений в свободной группе , Московский государственный университет ,1987( citește online ) (Teză de doctorat. 32,56MB)
- (ro) „ Limite inferioare la dimensiunea circuitelor de adâncime delimitate pe o bază completă cu adăugare logică ” , Note matematice ale Academiei de Științe ale URSS , vol. 41, nr . 4,Aprilie 1987, p. 333–338 ( DOI 10.1007 / BF01137685 )
- (ro) „Despre metoda aproximărilor” , în Proceedings of the 21st Annual ACM Symposium on theory of Computing , Seattle , Washington , SUA,Mai 1989, 167–176 p. ( DOI 10.1145 / 73007.73023 , citiți online [pdf. 1.41MB ])
- (ro) „ Limite inferioare ale complexității funcțiilor booleene simetrice ale circuitelor de redresare a contactelor ” , Note matematice ale Academiei de Științe din URSS , vol. 48, nr . 6,Decembrie 1990, p. 1226–1234 ( DOI 10.1007 / BF01240265 )
- (ro) (cu Stephen Rudich) , „Dovezi naturale” , în Proceedings of the 26th Simpozion anual ACM on theory of computing , Montreal , Quebec , Canada,Mai 1994, 204–213 p. , PostScript ( DOI 10.1145 / 195058.195134 , citiți online )
- (ro) „ Limite inferioare pentru calculul polinomial ” , Complexitate computațională , vol. 7, n o 4,decembrie 1998, p. 291–324 ( DOI 10.1007 / s000370050013 , citiți online [ ps ])
-
(ro) „ Complexitatea dovezilor propoziționale ” , Jurnalul ACM , vol. 50, n o 1,ianuarie 2003, p. 80–82 ( DOI 10.1145 / 602382.602406 , citiți online [ps] ) (Hârtie de sondaj pentru a 50-a aniversare a JACM)
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 ) .
-
(în) „ Câștigătorii Premiului Rolf Nevanlinna pentru Uniunea Internațională de Matematică ” [ arhivă27 decembrie 2008] (accesat la 20 ianuarie 2014 )
-
(în) „ EATCS: Premiul Gödel - 2007 ”
-
(în) „ Alexander Razborov ” pe site-ul Mathematics Genealogia Project
-
(în) „ Academia Rusă de Științe: Razborov Aleksandr Aleksandrovich: Informații generale: Istorie ”
-
(în) „ Unii oameni celebri cu numere finite de erdos: câștigători ai premiului Nevanlinna ”
-
Razborov: Despre densitatea minimă a triunghiurilor din grafice , Combinatorică, Probabilitate și Calcul } 17 (4): 603-618, 2008.
Vezi și tu
Articole similare
linkuri externe