Matemático ruso
Aleksandr Aleksandrovich Razborov ( ruso : Алекса́ндр Алекса́ндрович Разбо́ров ; nacido el 16 de febrero de 1963), a veces conocido como Sasha Razborov , es un matemático y teórico computacional soviético y ruso . Es Profesor de Servicio Distinguido Andrew McLeish en la Universidad de Chicago .
Investigación
En su trabajo más conocido, junto con Steven Rudich , introdujo el concepto de pruebas naturales , una clase de estrategias utilizadas para demostrar límites inferiores fundamentales en la complejidad computacional . En particular, Razborov y Rudich demostraron que, bajo el supuesto de que existen ciertos tipos de funciones unidireccionales , dichas pruebas no pueden dar una resolución del problema P = NP , por lo que se requerirán nuevas técnicas para resolver esta cuestión.
Premios
- Premio Nevanlinna (1990) por la introducción del "método de aproximación" para probar los límites inferiores del circuito booleano de algunos problemas algorítmicos esenciales , [1]
- Profesor Erdős , Universidad Hebrea de Jerusalén , 1998.
- Miembro correspondiente de la Academia Rusa de Ciencias (2000) [2] [3]
- Premio Gödel (2007, con Steven Rudich ) por el artículo " Pruebas naturales ". [4] [5]
- Premio David P. Robbins por el artículo "Sobre la densidad mínima de triángulos en gráficos" (Combinatorics, Probability and Computing 17 (2008), n.º 4, 603-618), y por la introducción de un nuevo y potente método, las álgebras de banderas, para resolver problemas en combinatoria extremal
- Profesor Gödel (2010) con la conferencia titulada Complejidad de las pruebas proposicionales. [6]
- Profesor de Servicio Distinguido Andrew MacLeish (2008) en el Departamento de Ciencias de la Computación, Universidad de Chicago .
- Miembro de la Academia Estadounidense de las Artes y las Ciencias (AAAS) (2020). [7]
Bibliografía
- Razborov, AA (1985). "Límites inferiores para la complejidad monótona de algunas funciones booleanas" (PDF) . Matemáticas soviéticas - Doklady . 31 : 354–357.
- Razborov, AA (junio de 1985). "Límites inferiores de la complejidad monótona de la constante lógica". Notas matemáticas de la Academia de Ciencias de la URSS . 37 (6): 485–493. doi :10.1007/BF01157687. S2CID 120875831.
- Разборов, Александр Александрович (1987). О системах уравнений в свободной группе (PDF) (en ruso). Universidad de Moscú . (Tesis doctoral. 32,56MB)
- Razborov, AA (abril de 1987). "Límites inferiores del tamaño de circuitos de profundidad acotados sobre una base completa con adición lógica". Notas matemáticas de la Academia de Ciencias de la URSS . 41 (4): 333–338. doi :10.1007/BF01137685. S2CID 121744639.
- Razborov, Alexander A. (mayo de 1989). "Actas del vigésimo primer simposio anual de la ACM sobre teoría de la computación - STOC '89". Actas del 21.º simposio anual de la ACM sobre teoría de la computación . Seattle , Washington , Estados Unidos. págs. 167–176. doi :10.1145/73007.73023. ISBN 0897913078.
- Razborov, AA (diciembre de 1990). "Límites inferiores de la complejidad de funciones booleanas simétricas de circuitos rectificadores de contacto". Notas matemáticas de la Academia de Ciencias de la URSS . 48 (6): 1226–1234. doi :10.1007/BF01240265. S2CID 120703863.
- Razborov, Alexander A.; Rudich, Stephen (mayo de 1994). "Actas del vigésimo sexto simposio anual de la ACM sobre teoría de la computación - STOC '94". Actas del 26.º simposio anual de la ACM sobre teoría de la computación . Montreal , Quebec , Canadá. págs. 204–213. doi :10.1145/195058.195134. ISBN 0897916638.
- Razborov, Alexander A. (diciembre de 1998). "Límites inferiores para el cálculo polinomial" (PostScript) . Computational Complexity . 7 (4): 291–324. CiteSeerX 10.1.1.19.2441 . doi :10.1007/s000370050013. S2CID 8130114.
- Razborov, Alexander A. (enero de 2003). "Complejidad de prueba proposicional" (PostScript) . Revista de la ACM . 50 (1): 80–82. doi :10.1145/602382.602406. S2CID 17351318. (Documento de encuesta con motivo del 50 aniversario del JACM)
Véase también
Notas
- ^ "Unión Matemática Internacional: Ganadores del premio Rolf Nevanlinna". Archivado desde el original el 17 de diciembre de 2007.
- ^ "Academia de Ciencias de Rusia: Razborov Aleksandr Aleksandrovich: Información general: Historia".
- ^ "Árbol genealógico de agencias rusas: R" (en ruso). Archivado desde el original el 21 de diciembre de 2007. Consultado el 15 de enero de 2008 .
- ^ "Premios y reconocimientos ACM-SIGACT: Premio Gödel 2007".
- ^ "EATCS: Premio Gödel - 2007". Archivado desde el original el 1 de diciembre de 2007.
- ^ "Conferenciantes Gödel – Asociación de Lógica Simbólica". Archivado desde el original el 8 de noviembre de 2021. Consultado el 10 de noviembre de 2021 .
- ^ "Se eligen miembros de la AAAS" (PDF) . Avisos de la American Mathematical Society .
Enlaces externos
