|
1985 – Richard M. Karp
Citation
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 algorithmic efficiency,
and, most notably, contributions to the theory of NP-completeness. 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.
[Home] [ACM Awards] [A. M. Turing Award]
|
