title: Aleksandr Razborov
text: # Aleksandr Razborov
  
  Aleksandr Aleksandrovič Razborov (Belovo, 16 febbraio 1963) è un matematico russo.
  
  È professore presso l'Università di Chicago.
  
  ## Ricerca
  
  Nel suo lavoro più noto, insieme a Steven Rudich, ha introdotto la nozione di dimostrazioni naturali, una classe di strategie utilizzate per dimostrare i limiti inferiori fondamentali nella complessità computazionale. In particolare, Razborov e Rudich hanno mostrato che, assumendo che esistano certi tipi di funzioni unidirezionali, tali dimostrazioni non possono dare una risoluzione del problema P = NP, quindi saranno necessarie nuove tecniche per risolvere questo problema.
  
  ## Premi
  
  * Premio Nevanlinna (1990) per aver introdotto il "metodo di approssimazione" nel dimostrare i limiti inferiori del circuito booleano di alcuni problemi algoritmici essenziali,
  * Docente di Erdős, Università Ebraica di Gerusalemme, 1998.
  * Membro corrispondente dell'Accademia delle scienze russa (2000)
  * Premio David P. Robbins per l'articolo "Sulla densità minima dei triangoli nei grafici" (Combinatorics, Probability and Computing 17 (2008), n. 4, 603–618), e per aver introdotto un nuovo potente metodo, flag algebras, per risolvere problemi di combinatoria estrema
  * Premio Gödel (2007, con Steven Rudich) per il documento "Natural Proofs".
  * Illustre professore di servizio (2008) presso il Dipartimento di Informatica, Università di Chicago.
  * Membro dell'American Academy of Arts and Sciences (AAAS) (2020).
  