Alan Selman

Alan Louis Selman (April 2, 1941 – January 22, 2021)^[1] was an American mathematician and theoretical computer scientist known for his research on structural complexity theory, the study of computational complexity in terms of the relation between complexity classes rather than individual algorithmic problems.^[2][3]

Selman was a graduate of the City College of New York. He earned a master's degree at the University of California, Berkeley before completing his Ph.D. in 1970 at Pennsylvania State University.^[4] His dissertation, Arithmetical Reducibilities and Sets of Formulas Valid in Finite Structures, was supervised by Paul Axt, a student of Stephen Cole Kleene.^[5]

He became a postdoctoral researcher at Carnegie Mellon University, and an assistant professor of mathematics at Florida State University, before moving to the computer science department of Iowa State University, eventually becoming a full professor there. In the late 1980s he moved to Northeastern University, becoming acting dean there, and in 1990 he moved again to the University at Buffalo as chair of computer science. He retired in 2014, and died on January 22, 2021.^[4]

He was the first chair of the annual Computational Complexity Conference,^[4] and served as editor-in-chief of the journal Theory of Computing Systems for 18 years,^[6] beginning in 2001.^[3]

Selman's research publications included well-cited works on the classification of different types of reductions according to their computational power, the formulation of promise problems, the complexity class UP of problems solvable by unambiguous Turing machines, and their applications to the computational complexity of cryptography:^[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