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 conocido por sus investigaciones 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ó 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, un 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ó de nuevo a la Universidad de Buffalo como presidente de informática. Se jubiló en 2014 y falleció el 22 de enero de 2021. [4]
Fue el primer presidente de la Conferencia Anual de Complejidad Computacional , [4] y se desempeñó como editor en jefe de la revista Theory of Computing Systems durante 18 años, [6] comenzando en 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 el 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 Fellow. [4] Fue nombrado miembro de la ACM en 1998, como "un colaborador influyente en 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 sobre Algoritmos y Teoría de la Computación de la Association for Computing Machinery ) le otorgó su Premio al Servicio Distinguido, destacando su trabajo en ayudar a fundar la Conferencia de Computación Computacional y en ayudar a financiar la investigación teórica en informática a través de su trabajo de redacción de informes de políticas para la National Science Foundation . [9]
La revista Theory of Computing Systems está organizando un número conmemorativo para celebrar su memoria. [6]