Richard Karp Featured in Les Dossiers de la Recherche

^{August 16, 2005}
An article about Richard Karp, head of the Algorithms Group, appeared in the August-October 2005 issue of the French journal Les Dossiers de la Recherche. Author Claire Kenyon, a professor at Brown University, discusses Karp's contributions in the area NP complete problems, which is the work he is most well known for, but adds, "there are few areas in computer science where he has not made an important contribution." A second article in the journal, entitled "What is P=NP" discusses Karp's contributions to demonstrating the significance of the P=NP problem which, roughly speaking, asks whether all the combinatorial problems in a very large class called NP can be solved by efficient algorithms. One of Karp's contributions in this area was showing that 21 problems well-known problems are NP-complete, which implies that, if any one of them can be solved efficiently, then all the problems in NP can be solved efficiently.