Alan Louis Selman (2 de abril de 1941 - 22 de enero de 2021) [1] fue un matemático e informático teórico 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 algoritmos individuales. problemas. [2] [3]
Selman se graduó en el 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 supervisada 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 trasladarse al departamento de informática de la Universidad Estatal de Iowa , donde finalmente se convirtió en profesor titular. A finales de la década de 1980 se trasladó a la Universidad Northeastern , donde se convirtió en decano interino, y en 1990 se trasladó nuevamente a la Universidad de Buffalo como catedrático 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 bien 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 solucionables por máquinas de Turing inequívocas y sus aplicaciones a la complejidad computacional de la criptografía : [2] [3]
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 becario Humboldt. [4] Fue nombrado miembro de ACM en 1998, como "un contribuyente influyente a la teoría de la complejidad computacional y un profesional dedicado dentro de la comunidad académica de 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 Maquinaria de Computación ) le otorgó su Premio al Servicio Distinguido, destacando su trabajo al ayudar a fundar la Conferencia sobre Complejidad Computacional y a financiar la informática teórica. investigación científica a través de su trabajo redactando informes de políticas para la Fundación Nacional de Ciencias . [9]
La revista Theory of Computing Systems organiza un número conmemorativo en homenaje a su memoria. [6]