Alan Selman

Alan Louis Selman (2 de abril de 1941 – 22 de enero de 2021) ^{[ 1 ]} fue un matemático y científico informático teórico estadounidense conocido por su investigación sobre la teoría de la complejidad estructural , el estudio de la complejidad computacional en términos de la relación entre clases de complejidad en lugar de problemas algorítmicos individuales. ^{[ 2 ] [ 3 ]}

Selman se graduó del City College de Nueva York . Obtuvo una maestría en la Universidad de California, Berkeley, antes de completar su doctorado en 1970 en la Universidad Estatal de Pensilvania . ^{[ 4 ]} Su disertación, Reducibilidades aritméticas y conjuntos de fórmulas válidas en estructuras finitas , fue dirigida por Paul Axt, estudiante de Stephen Cole Kleene . ^{[ 5 ]}

Se convirtió en investigador postdoctoral en la Universidad Carnegie Mellon y profesor asistente de matemáticas en la Universidad Estatal de Florida , antes de pasar al departamento de informática de la Universidad Estatal de Iowa , donde finalmente llegó a ser catedrático. A finales de la década de 1980 se trasladó a la Universidad Northeastern , donde fue decano interino, y en 1990 volvió a la Universidad de Buffalo como director del departamento de informática. Se jubiló en 2014 y falleció el 22 de enero de 2021. ^{[ 4 ]}

Fue el primer presidente de la Conferencia anual sobre Complejidad Computacional , ^{[ 4 ]} y se desempeñó como editor en jefe de la revista Theory of Computing Systems durante 18 años, ^{[ 6 ]} a partir de 2001. ^{[ 3 ]}

Las publicaciones de investigación de Selman incluyeron trabajos muy citados sobre la clasificación de diferentes tipos de reducciones según su poder computacional, la formulación de problemas de promesa , la clase de complejidad UP de problemas resolubles por máquinas de Turing no ambiguas y sus aplicaciones a la complejidad computacional de la criptografía : ^{[ 2 ] [ 3 ]}

• Ladner, RE ; Lynch, NA ; Selman, AL (1975), "Una comparación de reducibilidades en tiempo polinomial", Theoretical Computer Science , 1 (2): 103–123 , doi : 10.1016/0304-3975(75)90016-X , MR 0395319 
• Even, Shimon ; Selman, Alan L.; Yacobi, Yacov (1984), "La complejidad de los problemas de promesas con aplicaciones a la criptografía de clave pública", Information and Control , 61 (2): 159–173 , doi : 10.1016/S0019-9958(84)80056-X , MR 0772678 
• Grollmann, Joachim; Selman, Alan L. (1988), "Medidas de complejidad para criptosistemas de clave pública", SIAM Journal on Computing , 17 (2): 309–335 , doi : 10.1137/0217018 , MR 0935342 

Además de ser editor de varios volúmenes editados , Selman fue coautor del libro de texto Computability and Complexity Theory (con Steve Homer, Springer, 2001; 2.ª ed., 2011). ^{[ 7 ]}

Selman fue becario Fulbright y Humboldt . ^{[ 4 ]} Fue nombrado miembro de la ACM en 1998, como "un influyente contribuyente a la teoría de la complejidad computacional y un profesional dedicado dentro de la comunidad académica de la informática". ^{[ 8 ]} En 2002, ACM SIGACT (el Grupo de Interés Especial en Algoritmos y Teoría de la Computación de la Asociación para la Maquinaria de Computación ) le otorgó su Premio al Servicio Distinguido, reconociendo su trabajo en la fundación de la Conferencia de Complejidad Computacional y en la financiación de la investigación teórica en informática a través de su trabajo de redacción de informes de políticas para la Fundación Nacional de Ciencias . ^{[ 9 ]}

La revista Theory of Computing Systems está organizando un número conmemorativo para celebrar su memoria. ^{[ 6 ]}

• Publicaciones de Alan Selman indexadas por Google Académico