Richard Manning Karp Amerikkalainen matemaatikko ja tietotekniikan tutkija

Richard Manning Karp, (s. 3. tammikuuta 1935, Boston, Massachusetts, USA), amerikkalainen matemaatikko ja tietotekniikan tutkija ja vuoden 1985 AM Turing -palkinnon voittaja, tietokonetekniikan korkein kunnia "hänen jatkuvasta panoksestaan algoritmeja, mukaan lukien tehokkaiden algoritmien kehittäminen verkkovirran ja muiden kombinatoristen optimointiongelmien ratkaisemiseksi, polynomi-aika-laskettavuuden tunnistaminen algoritmisen tehokkuuden intuitiivisella käsitteellä ja etenkin panos NP-täydellisyyden teoriaan. " Hänen tutkimuskohteisiinsa ovat kuuluneet teoreettinen tietotekniikka, kombinatoriset algoritmit, diskreetti todennäköisyys, laskennallinen biologia ja Internet-algoritmit.

Karp ansaitsi kandidaatin tutkinnon (1955), maisterin tutkinnon (1956) ja tohtorin tutkinnon (1959), kaikki matematiikan, Harvardin yliopistosta. Opintojensa päätyttyä hän työskenteli matemaatikkona IBM: ssä (1959–68) ennen muuttoaan yliopistoon. Karp työskenteli Kalifornian yliopistossa Berkeleyssä (1968–1994), Washingtonin yliopistossa (1995–1990) ja jälleen Berkeleyssä (1999–), missä hän palasi yliopistoprofessoriksi.

Karpin vuoden 1972 artikkeli ”Reducibility among Combinatorial Problems” osoitti, että monet yleisesti tutkitut kombinatoriset ongelmat ovat saman ongelman variantteja, mikä tarkoittaa, että ne ovat kaikki todennäköisesti ratkaisemattomia (NP-täydelliset ongelmat - ts. Ongelmat, joille ei tunneta tehokasta ratkaisualgoritmia). Karp on Complicity of Computation (1974) -kirjailija ja hänellä on patentti tietyntyyppiselle monikytkentäiselle kytkentäverkolle.

Turing-palkinnon lisäksi Karp sai Fulkerson-palkinnon diskreetissä matematiikassa (1979), Yhdysvaltain kansallisen tiedemitalin (1996), Harvardin yliopiston satavuotismitalin (1997), Israelin tekniikan instituutin Harvey-palkinnon (1998), Carnegie Mellon University Dickson -palkinto tieteessä (2008) ja Japanin Kioton palkinto (2008). Hänet valittiin New Yorkin tiedeakatemiaan (1980), Yhdysvaltain kansalliseen tiedeakatemiaan (1980), Amerikan taiteen ja tieteen akatemiaan (1985), Yhdistelmätekniikan ja sen sovellusten instituuttiin (1990), Amerikan yhdistykseen. Tieteen eteneminen (1991), Yhdysvaltain kansallinen tekniikan akatemia (1992), Amerikan filosofinen yhdistys (1994), Ranskan tiedeakatemia (2002) ja Euroopan tiedeakatemia (2004).