b'\n_START_ARTICLE_\nRichard Karp\n_START_SECTION_\nBiografia\n_START_PARAGRAPH_\nN\xc4\x83scut \xc3\xaen familia lui Abraham \xc8\x99i a lui Rose Karp \xc3\xaen Boston, Massachusetts, Karp are trei fra\xc8\x9bi mai mici: Robert, David, and Carolyn. A studiat la Universitatea Harvard, unde a absolvit cursurile de licen\xc8\x9b\xc4\x83 \xc3\xaen 1955, cele de master \xc3\xaen 1956, \xc8\x99i a ob\xc8\x9binut doctoratul \xc3\xaen matematic\xc4\x83 aplicat\xc4\x83 \xc3\xaen 1959._NEWLINE_A \xc3\xaenceput s\xc4\x83 lucreze la IBM Thomas J. Watson Research Center de la IBM. \xc3\x8en 1968, a devenit profesor de informatic\xc4\x83, matematic\xc4\x83 \xc8\x99i cercetare opera\xc8\x9bional\xc4\x83 la University of California, Berkeley. \xc3\x8en afara unei perioade de patru ani petrecut\xc4\x83 ca profesor la Universitatea din Washington, a r\xc4\x83mas permanent la Berkeley. \xc3\x8entre 1988 \xc8\x99i 1995 \xc8\x99i din 1999 \xc3\xaencoace este \xc8\x99i cercet\xc4\x83tor la International Computer Science Institute din Berkeley, unde conduce grupul de algoritmi._NEWLINE_Richard Karp a primit Medalia Na\xc8\x9bional\xc4\x83 a \xc8\x98tiin\xc8\x9bei, \xc8\x99i este laureat al Premiului Harvey de la Technion \xc8\x99i a Medaliei Benjamin Franklin pe 2004 pentru informatic\xc4\x83 \xc8\x99i \xc8\x99tiin\xc8\x9be cognitive pentru descoperirile din domeniul teoriei complexit\xc4\x83\xc8\x9bii. \xc3\x8en 1994 a fost primit ca fellow al ACM._NEWLINE_\xc3\x8en 2012, Karp a devenit director fondator al Simons Institute for the Theory of Computing de la University of California, Berkeley.\n_START_SECTION_\nActivitatea\n_START_PARAGRAPH_\nA efectuat numeroase alte descoperiri importante \xc3\xaen informatic\xc4\x83 \xc8\x99i \xc3\xaen cercetarea opera\xc8\x9bional\xc4\x83 \xc3\xaen domeniul algoritmilor combinatorici. Interesele sale principale de cercetare cuprind \xc8\x99i bioinformatica._NEWLINE_\xc3\x8en 1971 a dezvoltat \xc3\xaempreun\xc4\x83 cu Jack Edmonds algoritmul Edmonds\xe2\x80\x93Karp de rezolvare a problemei debitului maxim \xc3\xaen re\xc8\x9bele, iar \xc3\xaen 1972 a publicat o lucrare esen\xc8\x9bial\xc4\x83 \xc3\xaen teoria complexit\xc4\x83\xc8\x9bii, "Reducibility Among Combinatorial Problems", \xc3\xaen care a demonstrat c\xc4\x83 21 de probleme sunt NP-complete._NEWLINE_\xc3\x8en 1973, \xc3\xaempreun\xc4\x83 cu John Hopcroft, a publicat algoritmul Hopcroft\xe2\x80\x93Karp, care \xc8\x99i ast\xc4\x83zi este cea mai rapid\xc4\x83 metod\xc4\x83 cunoscut\xc4\x83 de g\xc4\x83sire a cuplajelor de cardinalitate maxim\xc4\x83 \xc3\xaen grafurile bipartite._NEWLINE_\xc3\x8en 1980, \xc3\xaempreun\xc4\x83 cu Richard J. Lipton, Karp a demonstrat teorema Karp-Lipton, care arat\xc4\x83 c\xc4\x83, dac\xc4\x83 SAT poate fi rezolvat\xc4\x83 prin circuite booleene cu un num\xc4\x83r polinomial de por\xc8\x9bi logice, atunci ierarhia polinomial\xc4\x83 se pliaz\xc4\x83 la nivelul al doilea._NEWLINE_\xc3\x8en 1987, \xc3\xaempreun\xc4\x83 cu Michael O. Rabin, a dezvoltat algoritmul Rabin-Karp de c\xc4\x83utare \xc3\xaen \xc8\x99iruri de caractere.'