Alan Belmont Cobham (4 de noviembre de 1927 - 28 de junio de 2011) [1] fue un matemático y científico informático estadounidense conocido por (con Jack Edmonds y Michael O. Rabin ) inventar la noción de tiempo polinomial y la clase de complejidad P , [2] [B] por la tesis de Cobham que afirma que los problemas que tienen soluciones informáticas prácticamente utilizables se caracterizan por tener tiempo polinomial, [3] [B] y por el teorema de Cobham sobre los conjuntos de números que pueden ser reconocidos por autómatas finitos . [4] [C] También realizó un trabajo fundacional sobre secuencias automáticas , [5] [D] inventó las colas de prioridad y las estudió desde el punto de vista de la teoría de colas , [6] [A] y escribió un programa para jugar al bridge contractual que en ese momento (a mediados de la década de 1980) era uno de los mejores del mundo. [7]
Cobham fue estudiante en el Oberlin College , la Universidad de Chicago , la Universidad de California, Berkeley y el Instituto Tecnológico de Massachusetts , pero no completó un doctorado. Se convirtió en investigador de operaciones para la Armada de los Estados Unidos , investigador de IBM Research en el Centro de Investigación Thomas J. Watson y profesor y director fundador del departamento de informática de la Universidad Wesleyana . [1]