Alexander Razborov

Alexander Razborov (ruso: Алекса́ндр Алекса́ндрович Разбо́ров, Aleksandr Aleksandrovich Razborov), tamén coñecido como Sasha Razborov, nado o 16 de febreiro do 1963 en Belovo (Unión Soviética), é un matemático e teórico da computación ruso. Na actualidade, é profesor na Universidade de Chicago.

 Traxectoria 
Razborov é coñecido por introducir, xunto con Steven Rudich, a noción de proba natural, un tipo de estratexias para demostrar límites inferiores fundamentais en complexidade computacional. En concreto, ambos amosaron que, supoñendo a existencia de certas clases de funcións unidireccionais, as probas naturais non poden resolver o problema P versus NP.

 Premios 

 Premio Nevanlinna (1990).
 Premio Gödel (2007, con Steven Rudich).
 Premio David P. Robbins (2013).

 Publicacións 

 Razborov, A. A. (1985a). Lower bounds for the monotone complexity of some Boolean functions [Límites inferiores para a complexidade monótona dalgunhas funcións booleanas]. Soviet Mathematics - Doklady, 31, 354-357.
 Razborov, A. A. (1987). О системах уравнений в свободной группе [Sobre sistemas de ecuacións nun grupo libre]. Universidade Estatal de Moscova. Tese de doutoramento.
 Razborov, A. A.; Rudich, S. (1994). Natural proofs [Probas naturais]. Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 204-213.
 Razborov, A. A. (2003). Propositional proof complexity [Complexidade das probas proposicionais]. Journal of the ACM, 50 (1), 80-82.

 Notas 

Categoría:Científicos de Rusia
Categoría:Membros da Academia das Artes e das Ciencias dos Estados Unidos de América
Categoría:Alumnos da Universidade Estatal de Moscova
Categoría:Nados en 1963
Categoría:Matemáticos de Rusia