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 Categoría:Nados no óblast de Kemerovo