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, structure, space, models, and change. History On ...

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 (al ...

known for (with

Jack Edmonds Jack R. Edmonds (born April 5, 1934) is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, pol ...

) 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 In computational complexity theory, P, also known as PTIME or DTIME(''n''O(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, ...

, 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 Cobham's theorem is a theorem in combinatorics on words that has important connections with number theory, notably transcendental numbers, and automata theory. Informally, the theorem gives the condition for the members of a set ''S'' of natural nu ...

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 sequence In mathematics and theoretical computer science, an automatic sequence (also called a ''k''-automatic sequence or a ''k''-recognizable sequence when one wants to indicate that the base of the numerals used is ''k'') is an infinite sequence of terms ...

s, 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 o ...

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

Oberlin College Oberlin College is a Private university, private Liberal arts colleges in the United States, liberal arts college and conservatory of music in Oberlin, Ohio. It is the oldest Mixed-sex education, coeducational liberal arts college in the United S ...

, the

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

, 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 land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the ...

, 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 deci ...

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 org ...

at the

Thomas J. Watson Research Center The Thomas J. Watson Research Center is the headquarters for IBM Research. The center comprises three sites, with its main laboratory in Yorktown Heights, New York, U.S., 38 miles (61 km) north of New York City, Albany, New York and wit ...

, and a professor and founding department chair of the computer science department at

Wesleyan University Wesleyan University ( ) is a Private university, private liberal arts college, liberal arts university in Middletown, Connecticut. Founded in 1831 as a Men's colleges in the United States, men's college under the auspices of the Methodist Epis ...

Selected publications

References

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