Richard Karp: His influence and how to honor him

When I first saw the definition of NP-Complete I first thought if there are NP-complete problems I suspect they are contrived. When I saw the proof that  SAT is NP-complete I thought okay, so there is one natural problem  NP-complete by a trick of encoding, but I suspect there aren't any more.  I then read Karp's article that had 22 NP-complete problems. I thought okay, there are 22, but I suspect there are no more. No I didn't think that. But the point is that Cook and Karp together birthed modern complexity theory by introduction NP-completeness and showing that there are MANY natural problems that are NP-complete.

How many people has Richard Karp inspired? I don't know but I suspect it's a  cardinal between countable and the reals so it may depend on your model of set theory. Later in this post I will present Samir Khuller's story of how Richard Karp inspired him.

How to honor him?  The Simons inst. is currently welcoming contributions to the Richard M Karp Fund, which honors the scientific contributions of Founding Director Dick Karp. The fund will provide vital support for the mission and activities of the Simons institute. They have a deadline of Pi-Day. You can go here to contribute and/or here for a letter from Shafi Goldwasser, Prabhakar Raghavan, and Umesh Vazirani about the fund.

OKAY, Samir's story:

Mentoring and Influence via a Train Journey...

Almost to the day, 33 years ago I was running from my dorm room to catch an unreliable bus to the train station as I headed home for a mid-semester break.  On the way,I  stopped by the mailroom, and not knowing where to put the CACM that had just arrived,  stuffed it into the side of my bag and in the process, dropping my   notebook in the process. On the train, when I looked for my  notebook to go over  some material I realized it was missing! All I had was a CACM and a very long train ride. Skimming through the journal, I found Karp’s Turing Award article “Combinatorics, Complexity, and Randomness“. I  started reading this article, and was riveted! It was one of those life changing moments for me, when my immediate future became clear - I wanted to study Theoretical Computer Science and specifically the complexity of combinatorial problems. Without ever having met Dick Karp, he changed my life forever.

I met Dick long after he influenced me via his Turing Award Lecture and it was a real privilege to have had the opportunity to interview him via a fireside chat at Simons. See here.

I am delighted about the fund Bill mentions above as the money that goes to it will help inspire others as Karp inspired me.

Computational Complexity published first on Computational Complexity