Alan Belmont Cobham | |
|---|---|
| Born | November 4, 1927 |
| Died | June 28, 2011 (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 |
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]
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]
shallit was invoked but never defined (see the help page).kozen was invoked but never defined (see the help page).ausiello was invoked but never defined (see the help page).durand-rigo was invoked but never defined (see the help page).rowland was invoked but never defined (see the help page).miller was invoked but never defined (see the help page).truscott was invoked but never defined (see the help page).