Richard M. Karp

35 languages

Tools

From Wikipedia, the free encyclopedia

(Redirected from

)

Richard Manning Karp

Karp in 2009

Born

January 3, 1935

(age 91)

, US

Education

(

)

Known for

Awards

(1979)

(1985)

(1990)

(1995)

(1996)

(1998)

(2000)

(2004)

(2008)

Scientific career

Fields

Institutions

(1959)

Doctoral

students

Richard Manning Karp

(born January 3, 1935) is an American

and

at the

. He is most notable for his research in the

, for

which he received the 1985 ACM

, and the

in 2008.

Karp was elected a member of the

(1992) for

major contributions to the theory and application of NP-completeness,

constructing efficient combinatorial algorithms, and applying probabilistic

methods in computer science.

Biography

[

]

Born to parents Abraham and Rose Karp in

, Karp has three

younger siblings: Robert,

, and Carolyn. His family was

and he

grew up in a small apartment, in a then mostly Jewish neighborhood of

in Boston.

Both his parents were Harvard graduates (his mother eventually obtaining her

Harvard degree at age 57 after taking evening courses), while his father had

had ambitions to go to medical school after Harvard, but became a mathematics

teacher as he could not afford the medical school fees.

He attended

, where he received his bachelor's degree in 1955, his master's

degree in 1956, and his

in 1959. He started

working at

In 1968, Karp became professor of computer science, mathematics, and

operations research at the

. Karp was the

first associate chair of the Computer Science Division within the Department

of Electrical Engineering and Computer Science.

Apart from a 4-year period

as a professor at the

, he has remained at Berkeley.

From 1988 to 1995 and 1999 to the present he has also been a research

scientist at the

in Berkeley, where

he currently leads the Algorithms Group.

Richard Karp was awarded the

, and was the recipient

of the

and the 2004

Computer and Cognitive Science for his insights into

In 1994 he was inducted as a

of the

. He was elected to the 2002 class of

of the

He is the recipient of

several honorary degrees and a member of the U.S.

the

and the

In 2012, Karp became the founding director of the

at the

Work

[

]

Karp has made many important discoveries in computer science,

, and

. His major current research interests

include

In 1962 he co-developed with Michael Held the

, an

exponential-time algorithm for the

In 1971 he co-developed with

the

for

solving the

on networks, and in 1972 he published a

landmark paper in complexity theory, "Reducibility Among Combinatorial

Problems", in which he proved

In 1973 he and

published the

, the fastest known method for finding maximum

cardinality

In 1980, along with

, Karp proved the

(which proves that if

can be solved by

with a polynomial number of

, then the

collapses to its second

level).

In 1987 he co-developed with

the

Turing Award

[

]

His citation

for the

(1985)

Turing Award was as follows:

For his continuing contributions to the theory of algorithms including the development of efficient algorithms

for network flow and other combinatorial optimization problems, the identification of polynomial-time

computability with the intuitive notion of

, and, most notably, contributions to the

theory of

. Karp introduced the now standard methodology for proving problems to be NP-complete

which has led to the identification of many theoretical and practical problems as being computationally

difficult.

References

[

]

at the

Richard Manning Karp, Kyoto Prize Address, 2008

Karp, Richard.

www2.eecs.berkeley.edu

. Retrieved

1 December

2021

, retrieved

2019-10-09

www.nasonline.org

. Retrieved

2022-02-22

. Retrieved

2022-02-22

search.amphilsoc.org

. Retrieved

2022-02-22

. 30 April 2012

. Retrieved

23 October

2016

Richard M. Karp (1972).

(PDF)

. In R. E. Miller; J. W. Thatcher (eds.).

Complexity of Computer Computations

. New York: Plenum. pp.

85–

103. Archived from

(PDF)

on 2011-06-29

. Retrieved

2010-01-17

Association for Computing Machinery.

. Archived from

on 2012-07-03

Retrieved

2010-01-17

External links

[

]

Wikimedia Commons has media

related to

from the Institute for Operations Research and the

Management Sciences

Preceded by

Benjamin Franklin Medal in Computer and

Cognitive Science

2004

Succeeded by

laureates

(2000)

(2001)

(2002)

(2003)

(2004)

(2005)

(2006)

(2007)

(2008)

(2009)

(2010)

(2011)

(2012)

(2013)

(2014)

(2015)

(2016)

(2017)

(2018)

(2019)

(2020)

(2021)

(2022)

(2023)

(2024)

laureates

(1966)

(1967)

(1968)

(1969)

(1970)

(1971)

(1972)

(1973)

(1974)

(1975)

(1976)

(1977)

(1978)

(1979)

(1980)

(1981)

(1982)

(1983)

(1984)

(1985)

(1986)

(1987)

(1988)

(1989)

(1990)

(1991)

(1992)

(1993)

(1994)

(1995)

(1996)

(1997)

(1998)

(1999)

(2000)

(2001)

(2002)

(2003)

(2004)

(2005)

(2006)

(2007)

(2008)

(2009)

(2010)

(2011)

(2012)

(2013)

(2014)

(2015)

(2016)

(2017)

(2018)

(2019)

(2020)

(2021)

(2022)

(2023)

(2024)

(2025)

Laureates of the

Behavioral and social science

1960s

1964

1980s

1986

1987

1988

1990s

1990

1991

1992

1994

1995

1996

1997

1998

1999

2000s

2000

2003

2004

2005

2008

2009

2010s

2011

2014

2015

2020s

2023

2025

Biological sciences

1960s

1963

1964

1965

1966

1967

1968

1969

1970s

1970

1973

1974

1975

1976

1979

1980s

1981

1982

1983

1986

1987

1988

1989

1990s

1990

1991

1992

1993

1994

1995

1996

1997

1998

1999

2000s

2000

2001

2002

2003

2004

2005

2006

2007

2008

2009

2010s

2010

2011

2012

2013

2014

2020s

2023

2025

Chemistry

1960s

1964

1980s

1982

1983

1986

1987

1988

1989

1990s

1990

1991

1992

1993

1994

1995

1996

1997

1998

1999

2000s

2000

2001

2002

2004

2005

2006

2007

2008

2009

2010s

2010

2011

2012

2013

2014

2025

Engineering sciences

1960s

1962

1963

1964

1965

1966

1967

1968

1969

1970s

1970

1973

1974

1975

1976

1979

1980s

1982

1983

1986

1987

1988

1989

1990s

1990

1991

1992

1993

1994

1995

1996

1998

1999

2000s

2000

2001

2002

2003

2004

2005

2006

2007

2008

2009

2010s

2010

2011

2012

2020s

2023

2025

Mathematical, statistical, and computer sciences

1960s

1963

1964

1965

1966

1967

1968

1969

1970s

1970

1973

1974

1975

1976

1979

1980s

1982

1983

1986

1987

1988

1989

1990s

1990

1991

1992

1993

1994

1995

1996

1997

1998

1999

2000s

2000

2001

2002

2003

2004

2005

2006

2007

2009

2010s

2010

2011

2012

2013

2020s

2025

Physical sciences

1960s

1963

1964

1965

1966

1967

1968

1969

1970s

1970

1973

1974

1975

1976

1979

1980s

1982

1983

1986

1987

1988

1989

1990s

1990

1991

1992

1993

1994

1995

1996

1997

1998

1999

2000s

2000

2001

2002

2003

2004

2005

2006

2007

2008

2009

2010s

2011

2012

2014

2020s

2023

2025

(1960)

(1961)

(1962)

(1963)

(1964)

(1965)

(1966)

(1967)

(1968)

(1969)

(1970)

(1971)

(1974)

(1975)

(1976)

(1977)

(1978)

(1979)

(1980)

(1981)

(1982)

(1983)

(1984)

(1985)

(1986)

(1987)

(1988)

(1989)

(1990)

(1992)

(1994)

(1996)

(1997)

(1998)

(1999)

(2000)

(2001)

(2002)

(2003)

(2004)

(2005)

(2006)

(2007)

(2008)

(2009)

(2010)

(2011)

(2012)

(2013)

(2014)

(2015)

(2016)

(2017)

(2018)

(2019)

(2020)

(2021)

(2022)

(2023)

(2024)

1975–1999

(1975)

(1976)

(1977)

(1978)

(1979)

(1980)

(1981)

(1982)

(1983)

(1984)

(1985)

(1986)

(1987)

(1988)

(1989)

(1990)

(1991)

(1992)

(1993)

(1994)

(1995)

(1996)

(1997)

(1998)

(1999)

2000–present

(2000)

(2001)

(2002)

(2003)

(2004)

(2005)

(2006)

(2007)

(2008)

(2009)

(2010)

(2011)

(2012)

(2013)

(2014)

(2015)

(2016)

(2017)

(2018)

(2019)

(2020)

(2021)

(2022)

(2023)

International

National

Academics

People

Other

This page was last edited on 17 May 2026, at 00:36

(UTC)

Text is available under the

; additional terms may apply. By using this site, you agree to the

and

. Wikipedia® is a registered trademark of the

, a non-profit organization.