Richard Manning Karp Matematician american și informatician

Richard Manning Karp, (n. 3 ianuarie 1935, Boston, Mass., SUA), matematician și om de informatică american și câștigător al premiului Turing AM din 1985, cea mai înaltă onoare în informatică, pentru „contribuțiile sale continue la teoria algoritmi incluzând dezvoltarea algoritmilor eficienți pentru fluxul de rețea și alte probleme de optimizare combinatorie, identificarea computabilității polinomiale în timp cu noțiunea intuitivă de eficiență algoritmică și, mai ales, contribuții la teoria completitudinii NP. " Interesele sale de cercetare au inclus informatica teoretică, algoritmi combinativi, probabilitate discretă, biologie computatională și algoritmi de internet.

Karp a obținut o diplomă de licență (1955), un master (1956) și un doctorat (1959), toate în matematică, de la Universitatea Harvard. După ce și-a încheiat studiile, a lucrat ca matematician la IBM (1959–68) înainte de a se muta în mediul academic. Karp a ocupat funcții la Universitatea din California, Berkeley (1968–94), la Universitatea din Washington (1995–99), iar din nou la Berkeley (1999–), unde s-a întors ca profesor universitar.

Lucrarea de Karp din 1972 „Reductibilitatea printre problemele combinative” a dovedit că multe probleme combinatoriale studiate frecvent sunt variante ale aceleiași probleme, ceea ce implică că sunt toate probabil intractabile (probleme complete NP - adică probleme pentru care nu se cunoaște niciun algoritm eficient de soluție). Karp este autorul Complexity of Computation (1974) și deține un brevet pentru un tip de rețea de comutare multiconectare.

Pe lângă premiul Turing, Karp a primit Premiul Fulkerson în Matematică Discretă (1979), Medalia Națională a Științei a SUA (1996), Medalia Centenarului Universității Harvard (1997), Premiul Harvey al Institutului Israel de Tehnologie (1998), Premiul Dickson în știință al Universității Carnegie Mellon (2008) și Premiul Kyoto al Japoniei (2008). A fost ales la New York Academy of Sciences (1980), la American National Academy of Sciences (1980), la American Academy of Arts and Sciences (1985), la Institute of Combinatorics and Applications Applications (1990), la American Association Advanced of Science (1991), Academia Națională de Inginerie a SUA (1992), Societatea Americană de Filozofie (1994), Academia Franceză de Științe (2002) și Academia Europeană de Științe (2004).