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.[1] Na actualidade, é profesor na Universidade de Chicago.[1]
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.[2]
Premios
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.[5]
- 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
