Richard Manning Karp Matematico e scienziato informatico americano

Richard Manning Karp, (nato il 3 gennaio 1935, Boston, Massachusetts, USA), matematico e scienziato informatico americano e vincitore del premio AM Turing del 1985, il più alto riconoscimento nell'informatica, per "i suoi continui contributi alla teoria di algoritmi che includono lo sviluppo di algoritmi efficienti per il flusso di rete e altri problemi di ottimizzazione combinatoria, l'identificazione della calcolabilità del tempo polinomiale con la nozione intuitiva di efficienza algoritmica e, in particolare, i contributi alla teoria della completezza NP ”. I suoi interessi di ricerca includono informatica teorica, algoritmi combinatori, probabilità discreta, biologia computazionale e algoritmi Internet.

Karp ha conseguito una laurea (1955), un master (1956) e un dottorato (1959), tutti in matematica, presso l'Università di Harvard. Dopo aver terminato gli studi, ha lavorato come matematico presso IBM (1959-1968) prima di trasferirsi nel mondo accademico. Karp ha ricoperto incarichi presso l'Università della California, Berkeley (1968-1994), l'Università di Washington (1995-1999), e ancora presso Berkeley (1999–), dove è tornato come professore universitario.

L'articolo del Karp del 1972 "Riducibilità tra i problemi combinatori" ha dimostrato che molti problemi combinatori comunemente studiati sono varianti dello stesso problema, il che implica che sono probabilmente tutti intrattabili (problemi NP-completi, cioè problemi per i quali non è noto alcun algoritmo di soluzione efficiente). Karp è l'autore di Complexity of Computation (1974) e detiene un brevetto per un tipo di rete di commutazione multiconnessione.

Oltre al Turing Award, Karp ha ricevuto il Premio Fulkerson in Discrete Mathematics (1979), la US National Medal of Science (1996), la Harvard University Centennial Medal (1997), il Israel Institute of Technology Harvey Prize (1998), il Premio Dickson in Science dell'Università Carnegie Mellon (2008) e Premio giapponese di Kyoto (2008). È stato eletto alla New York Academy of Sciences (1980), alla US National Academy of Sciences (1980), all'American Academy of Arts and Sciences (1985), all'Institute of Combinatorics and Its Applications (1990), all'American Association for Advancement of Science (1991), US National Academy of Engineering (1992), American Philosophical Society (1994), French Academy of Sciences (2002) e European Academy of Sciences (2004).