Alan Cobham

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

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.

Selected publications