Alan Belmont Cobham (4 November 192728 June 2011) was an American

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...

and

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus ( ...

known for (with Jack Edmonds) inventing the notion of

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

and the complexity class P, for

Cobham's thesis Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds),.. asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is ...

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 A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...

. He also did foundational work on automatic sequences, invented

priority queue In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a ''priority'' associated with it. In a priority queue, an element with high priority is se ...

s and studied them from the point of view of

queueing theory Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...

, and wrote a program for playing

contract bridge Contract bridge, or simply bridge, is a trick-taking card game using a standard 52-card deck. In its basic format, it is played by four players in two competing partnerships, with partners sitting opposite each other around a table. Millions ...

that was at the time (in the mid-1980s) one of the best in the world. Cobham was a student at Oberlin College, the

University of Chicago The University of Chicago (UChicago, Chicago, U of C, or UChi) is a private university, private research university in Chicago, Illinois. Its main campus is located in Chicago's Hyde Park, Chicago, Hyde Park neighborhood. The University of Chic ...

, the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...

, and the

Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a Private university, private Land-grant university, land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern t ...

, but did not complete a doctorate. He became an

operations research Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve dec ...

er for the

United States Navy The United States Navy (USN) is the maritime service branch of the United States Armed Forces and one of the eight uniformed services of the United States. It is the largest and most powerful navy in the world, with the estimated tonnage ...

, a researcher for

IBM Research IBM Research is the research and development division for IBM, an American multinational information technology company headquartered in Armonk, New York, with operations in over 170 countries. IBM Research is the largest industrial research or ...

at the Thomas J. Watson Research Center, and a professor and founding department chair of the computer science department at

Wesleyan University Wesleyan University ( ) is a private liberal arts university in Middletown, Connecticut. Founded in 1831 as a men's college under the auspices of the Methodist Episcopal Church and with the support of prominent residents of Middletown, the c ...

Selected publications

References

1927 births 2011 deaths American mathematicians Theoretical computer scientists IBM Research computer scientists Wesleyan University faculty {{US-mathematician-stub