Karp, Richard Manning

Karp, Richard Manning, 3. 1. 1935 Boston, Massachusetts — americký matematik a informatik. R. 1959 – 68 pôsobil vo Výskumnom centre Thomasa J. Watsona spoločnosti IBM, 1968 – 94 a od 1999 ako profesor na Kalifornskej univerzite v Berkeley, 1994 – 99 na Washingtonskej univerzite, súčasne 1988 – 95 a od 1999 v International Computer Science Institute v Berkeley. Zaoberá sa problémami z oblasti paralelných algoritmov, výpočtovej zložitosti, operačnej analýzy a bioinformatiky. Je podľa neho nazvaných viacero algoritmov, metód a viet, na ktorých sa autorsky podieľal, napr. Edmondsov-Karpov algoritmus na hľadanie maximálneho toku v sieťach (1971, s kanadským matematikom Jackom Edmondsom, *1934), Hopcroftov-Karpov algoritmus na hľadanie max. počtu spojení v bipartitných grafoch (1973, s J. Hopcroftom), Karpova-Liptonova veta z obl. teórie zložitosti (1980, s Richardom J. Liptonom, *1946). R. 1972 uviedol v článku Redukovateľnosť kombinatorických problémov (Reducibility Among Combinatorial Problems) dôkazy o NP-úplnosti 21 problémov z oblasti výpočtovej zložitosti (→ NP-úplný problém). Spoluautor 17 kníh, napr. Paralelné algoritmy pre stroje so spoločnou pamäťou (Parallel Algorithms for Shared-Memory Machines, 1990). Člen viacerých národných akadémií vied (napr. USA, Francúzska). Nositeľ mnohých významných ocenení, napr. Turingovej ceny (1985), Kjótskej ceny (2008).