Alan Cobham (mathematician)

Alan Belmont Cobham (4 November 1927 – 28 June 2011)^[1] was an American mathematician and computer scientist known for (with Jack Edmonds and Michael O. Rabin) inventing the notion of polynomial time and the complexity class P,^[2][B] for Cobham's thesis stating that the problems that have practically usable computer solutions are characterized by having polynomial time,^[3][B] and for Cobham's theorem on the sets of numbers that can be recognized by finite automata.^[4][C] He also did foundational work on automatic sequences,^[5][D] invented priority queues and studied them from the point of view of queueing theory,^[6][A] and wrote a program for playing contract bridge that was at the time (in the mid-1980s) one of the best in the world.^[7]

Alan Belmont Cobham
Born	(1927-11-04)November 4, 1927
Died	June 28, 2011(2011-06-28) (aged 83)
Nationality	American
Occupation	Theoretical computer scientist
Known for	Defining the class P, Cobham's thesis, Cobham's theorem, inventing priority queues, writing a program to play contract bridge

Cobham was a student at Oberlin College, the University of Chicago, the University of California, Berkeley, and the Massachusetts Institute of Technology, but did not complete a doctorate. He became an operations researcher for the United States Navy, a researcher for IBM Research at the Thomas J. Watson Research Center, and a professor and founding department chair of the computer science department at Wesleyan University.^[1]

Selected publications

A.	Cobham, Alan (February 1954). "Priority assignment in waiting line problems". Journal of the Operations Research Society of America. 2 (1): 70–76. doi:10.1287/opre.2.1.70.

B.

Cobham, Alan (1965). "The intrinsic computational difficulty of functions". In Bar-Hillel, Yehoshua (ed.). Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress. Studies in Logic and the Foundations of Mathematics. Amsterdam: North-Holland. pp. 24–30. MR 0207561.

C.	Cobham, Alan (June 1969). "On the base-dependence of sets of numbers recognizable by finite automata". Mathematical Systems Theory. 3 (2): 186–192. doi:10.1007/BF01746527. MR 0250789. S2CID 19792434.

D.	Cobham, Alan (March 1972). "Uniform tag sequences". Mathematical Systems Theory. 6 (1–2): 164–192. doi:10.1007/BF01706087. MR 0457011. S2CID 28356747.