Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111

1. 0:00 – 3:50

   Introduction

   1. LFLex Fridman0:00

      The following is a conversation with Richard Karp, a professor at Berkeley and one of the most important figures in the history of theoretical computer science. In 1985, he received the Turing Award for his research in the theory of algorithms, including the development of the Admans-Karp algorithm for solving the max flow problem on networks, Hopcroft-Karp algorithm for finding maximum cardinality matchings in bipartite graphs, and his landmark paper in complexity theory called Reducibility Among Combinatorial Problems, in which he proved 21 problems to be NP-complete. This paper was probably the most important catalyst in the explosion of interest in the study of NP-completeness and the P versus NP problem in general. Quick summary of the ads. Two sponsors, Eight Sleep mattress and Cash App. Please consider supporting this podcast by going to eightsleep.com/lex and downloading Cash App and using code LEXPODCAST. Click the links, buy the stuff. It really is the best way to support this podcast. If you enjoy this thing, subscribe on YouTube, review it with five stars on Apple Podcast, support it on Patreon, or connect with me on Twitter @LexFridman. As usual, I'll do a few minutes of ads now and never any ads in the middle that can break the flow of the conversation. This show is sponsored by Eight Sleep and its Pod Pro mattress that you can check out at eightsleep.com/lex to get $200 off. It controls the temperature with an app. It can cool down to as low as 55 degrees on each side of the bed separately. Research shows that temperature has a big impact on the quality of our sleep. Anecdotally, it's been a game-changer for me. I love it. It's been a couple weeks now. I've just been really enjoying it, both in the fact that I'm getting better sleep and that it's a smart mattress, essentially. I kind of imagine this being the early days of artificial intelligence being a part of every aspect of our lives. And certainly infusing AI in one of the most important aspects of life, which is sleep, I think has a lot of potential for being beneficial. The Pod Pro is packed with sensors that track heart rate, heart rate variability, and respiratory rate, showing it all in their app. The app's health metrics are amazing, but the cooling alone is honestly worth the money. I don't always sleep, but when I do, I choose the Eight Sleep Pod Pro mattress. Check it out at eightsleep.com/lex to get $200 off. I remember just visiting the site and considering a purchase helps convince the folks at Eight Sleep that this silly old podcast is worth sponsoring in the future. This show is also presented by the great and powerful Cash App, the number one finance app in the App Store. When you get it, use code LEXPODCAST. Cash App lets you send money to friends, buy Bitcoin, and invest in the stock market with as little as $1. It's one of the best designed interfaces of an app that I've ever used. To me, good design is when everything is easy and natural. Bad design is when the app gets in the way, either because it's buggy or because it tries too hard to be helpful. I'm looking at you Clippy from Microsoft, even though I love you. Anyway, there's a big part of my brain and heart that loves to design things and also to appreciate great design by others. So again, if you get Cash App from the App Store or Google Play and use the code LEXPODCAST, you get $10 and Cash App will also donate $10 to FIRST, an organization that is helping to advance robotics and STEM education for young people around the world. And now here's my conversation with Richard Karp.

2. 3:50 – 9:46

   Geometry

   1. LFLex Fridman3:50

      You wrote that at the age of 13, you were first exposed to plane geometry and was wonderstruck by the power and elegance of formal proofs. Are there problems, proofs, properties, ideas in plane geometry that, uh, from that time that you remember, uh, being mesmerized by or just enjoying to go through to prove various aspects?

   2. RKRichard Karp4:13

      So Michael Rabin told me this story about an experience he had when he was a young student who was ex- tossed out of his classroom for bad behavior and was wandering through the corridors of his school and came upon two older students who were studying the problem of finding the shortest distance between two non-overlapping circles. And Michael thought about it and then said, "Um, you take the straight line between the two centers and the segment between the two circles is the shortest, because a straight line is the shortest distance between the two centers. And any other line connecting the circles would be, uh, on a sh- on a longer line." And I thought, and he thought, and I agreed that this was just elegant that pure reasoning could come up with such a result.

   3. LFLex Fridman5:17

      Certainly, the, the shortest distance from the two centers of the circles is a straight line. Uh, could you once again say what's the next step in that proof?

   4. RKRichard Karp5:30

      Well, any, any segment joining the, the c- the two circles, uh, if you extend it by taking the radius on each side, you get a segment with, uh, a path with three edges which connects the two centers. And this has to be at least as long as the shortest path, which is the straight line.

   5. LFLex Fridman5:53

      The straight line, yeah. Wow, th- yeah, that is, that's quite, quite simple. So what, what is it about that elegance that you just find, uh, compelling?

   6. RKRichard Karp6:04

      W- Well, just that you could...... establish a, uh, a fact about geometry beyond dispute by pure reasoning.

   7. LFLex Fridman6:16

      (laughs)

   8. RKRichard Karp6:17

      Um, I, I also enjoyed the challenge of solving puzzles in plane geometry. It was much more fun than the earlier mathematics courses which were mostly about arithmetic operations and manipulating them.

   9. LFLex Fridman6:33

      Was, was there something about geometry itself that's slightly visual component of it? That you can visualize-

   10. RKRichard Karp6:39

       Oh, oh, yes.

   11. LFLex Fridman6:39

       ... that

   12. NANarrator6:39

       was compelling?

   13. RKRichard Karp6:39

       Absolutely. Although I lacked three-dimensional vision. I wasn't very good at three-dimensional vision. And-

   14. LFLex Fridman6:47

       You mean being able to visualize three-dimensional objects?

   15. RKRichard Karp6:49

       Three-dimensional objects or, or, um, uh, surfaces, hyper planes, and so on. Um, so, so there, uh, there I didn't have an intuition. But, um, for example, the fact that the sum of the angles of a triangle is 180 degrees, uh, is pr- is proved convincingly, um, and it's comes as a surprise that that can be done. (laughs)

   16. LFLex Fridman7:21

       Why, why is that surprising? The, the-

   17. RKRichard Karp7:25

       Well-

   18. LFLex Fridman7:25

       Well, it is a surprising, uh, is a surprising idea, I suppose. Uh, why does that prove difficult?

   19. RKRichard Karp7:32

       It's not. That's the point. It's so easy and yet it's so convincing.

   20. LFLex Fridman7:37

       Do you remember what is the proof? That it's um, uh-

   21. RKRichard Karp7:40

       Um, yeah.

   22. LFLex Fridman7:40

       ... sums up, adds up to 180.

   23. RKRichard Karp7:42

       Uh, you, you start at a corner and, and draw a line, um, parallel to the opposite side. And that line sort of trisects the angle between the other two sides. And, uh, you, you, you get a, uh, a half plane which has to add up to 180 degrees and it consist- and the angles by, by the equality of, uh, alternate angles. What's it called? Um, you, you, you get a correspondence between the angles created by the side- along the side of the triangle and the three angles of the triangle.

   24. LFLex Fridman8:34

       Has geometry had an impact on, when you look into the future of your work with combinatorial algorithms, has it had some kind of impact? In terms of, yeah, being able- the, the puzzles, the visual aspects that were first so compelling to you?

   25. RKRichard Karp8:51

       Not Euclidean geometry, particularly. I think, uh, uh, I use tools like linear programming and integer programming a lot. And, uh, but, uh, those require high dimensional visualization. And so I tend to go by the algebraic properties. Um-

   26. LFLex Fridman9:13

       Right. The, you, you go by the algebra- the linear algebra and not by the, the visualization?

   27. RKRichard Karp9:19

       Not by... Well, the interpretation in terms of, for example, finding the highest point on a polyhedron-

   28. LFLex Fridman9:26

       Mm-hmm.

   29. RKRichard Karp9:26

       ... as in, uh, linear programming, uh, is, is motivating. Um, but again, it, I, I don't have the high dimensional intuition that would particularly inform me. So I sort of deepen... lean on the algebra.

   30. LFLex Fridman9:44

       So to linger on that point,

3. 9:46 – 13:00

   Visualizing an algorithm

   1. LFLex Fridman9:46

      what kind of visualization do you, like, do you do when you're trying to think about... we'll get to combinatorial algorithms, but just algorithms in general.

   2. RKRichard Karp9:57

      Yeah.

   3. LFLex Fridman9:57

      What kinda, what, what's inside your mind when you're thinking about designing algorithms? Or, or even just-

   4. RKRichard Karp10:05

      Uh-

   5. LFLex Fridman10:05

      ... tackling any, any mathematical problem?

   6. RKRichard Karp10:09

      Well, I think that usually an algorithm is, involves a, uh, repetition of some inner loop.

   7. LFLex Fridman10:19

      (laughs)

   8. RKRichard Karp10:19

      And, and so I can sort of visualize the, um, the distance from the desired solution as iteratively reducing until you finally hit the exact solution.

   9. LFLex Fridman10:33

      And try to take steps that get you closer to the-

   10. RKRichard Karp10:35

       Try to get-

   11. LFLex Fridman10:36

       ... the-

   12. RKRichard Karp10:36

       ... take steps that get closer and having the certainty of converging. So it's, it's very, it's, it's basically the, the mechanics of the algorithm is often very simple. Um, but, uh, especially when you're trying something out on the computer. So for example, um, uh, I did some work on the traveling salesman problem, and, um, I could see there was a particular function that had to be minimized. And it was fascinating to see the successive approaches to the minimum, to the optimum.

   13. LFLex Fridman11:12

       You mean... So first of all, a traveling salesman problem is where you have to visit, uh, every city without ever... only once.

   14. RKRichard Karp11:21

       Yeah, that's right.

   15. LFLex Fridman11:22

       Okay.

   16. RKRichard Karp11:22

       Find the shortest path through-

   17. LFLex Fridman11:23

       The shortest path.

   18. RKRichard Karp11:23

       ... a set of cities.

   19. LFLex Fridman11:24

       And, yeah. Uh, which is sort of a canonical, a standard, a really nice problem that's really hard.

   20. RKRichard Karp11:30

       Right.

   21. LFLex Fridman11:30

       In computer science.

   22. RKRichard Karp11:31

       That's, exactly.

   23. LFLex Fridman11:32

       (laughs)

   24. RKRichard Karp11:32

       Yes.

   25. LFLex Fridman11:32

       Uh, so c- can you say again what was nice about the objective fu- uh, being able to think about the objective function there and maximizing it or minimizing it?

   26. RKRichard Karp11:41

       Well, just so that the, um, as the algorithm proceeded, it was-

   27. LFLex Fridman11:47

       Mm-hmm.

   28. RKRichard Karp11:47

       ... you were making progress, continual progress. And, uh, and eventually getting to the optimum point.

   29. LFLex Fridman11:54

       So there's two, two parts maybe. Maybe you can correct me, but first is, like, getting an intuition about what the solution will look like, and, or even maybe coming up with a solution, and two is proving that this thing is actually going to be pretty good. Uh, what part is harder for you?... where does the magic happen? Is it in the first sets of intuitions or is it in the detail- the messy details of actually showing that it is going to get to the exact solution and it's gonna run at this- at, at a certain complexity?

   30. RKRichard Karp12:32

       Well, the- the ma- the magic is just the fact that it- th- that the gap from the optimum decreases monotonically, and you can see it happening and, um, various metrics of what's going on are improving a- all along, until finally, you hit the optimum. Perhaps later we'll talk about the assignment problem, and I can-
4. 13:00 – 18:06

   A beautiful algorithm

   1. RKRichard Karp13:00

   2. LFLex Fridman13:00

      Now zooming out again, as you write, "Don Knuth has called attention to a breed of people who, uh, derive great aesthetic pleasure from contemplating the structure of computational processes." So Don calls these folks geeks.

   3. RKRichard Karp13:16

      Mm-hmm.

   4. LFLex Fridman13:16

      And you write that you remember the moment you realized you were such a person, you were shown the Hungarian algorithm to solve the assignment problem.

   5. RKRichard Karp13:25

      Right.

   6. LFLex Fridman13:25

      So perhaps you can explain what the assignment problem is and what, uh, the Hungarian algorithm is?

   7. RKRichard Karp13:33

      So in the assignment problem, you have, uh, n boys and n girls, and you are given the desirability of, uh, or- or the cost of matching the i-th boy with the j-th girl for all i and j. You're given a matrix of numbers and you want to find the one-to-one matching of the boys with the girls, such that the sum of the associated cost will be minimized. So the- the- the best way to match the boys with the girls, or men with jobs, or any two sets. Um-

   8. LFLex Fridman14:18

      Now, any possible matching is possible, or there are some restraints?

   9. RKRichard Karp14:21

      Uh, yeah, all- all one-to-one correspondences are permi- permissible. If there is a connection that is not allowed, then you can think of it as having an infinite cost.

   10. LFLex Fridman14:32

       I see, yeah. Right.

   11. RKRichard Karp14:34

       So, um, what you do is, uh, to depend on the observation that the identity of the optimal assignment, or as we call it, the optimal permutation, um, is not changed if you subtract, um, a constant from any row or column of the matrix. You can see that the comparison between the different assignments is not changed by that. Um, because you're pino- if you decrease a particular row, all the elements of a row by some constant, all solutions decrease by the cost of that- by an amount equal to that constant. So the idea of the algorithm is to start with a matrix of non-negative numbers and keep subtracting from rows or from- or- or entire columns, um, in- in such a way that you subtract the- the same constant from all the elements of that row or column, uh, while maintaining the property that, um, uh, all the elements are non-negative.

   12. LFLex Fridman15:58

       Simple.

   13. RKRichard Karp15:59

       Yeah. And so- and so, um, what you have to do is, uh, is find small moves which will decrease the total cost, um, while, uh, subtracting constants from rows or columns. And there's a particular way of doing that by computing the kind of shortest path through the elements in the matrix. Uh, and you just keep going in this way, um, until you finally get a- a full permutation of zeros while the matrix is non-negative, and then you know that that has to be the cheapest.

   14. LFLex Fridman16:38

       Is that as, um, simple as it sounds? So the-

   15. RKRichard Karp16:43

       Well-

   16. LFLex Fridman16:43

       ... the shortest path to the matrix part?

   17. RKRichard Karp16:45

       Yeah. The simplicity lies in how you find the- what you- I oversimplified slightly what you- you- you will end up, uh, subtracting a constant from some rows or columns and adding, uh, the same constant back to other rows and columns, uh, so as not to, uh, not- not to reduce any of the zero elements. Le- you leave them unchanged. Um, but, um, uh, each individual step modifies a s- a s- a sev- several rows and columns by the same amount, but overall, it decreases the cost.

   18. LFLex Fridman17:26

       So there's something about that elegance that made you go, "Aha, this is a beautiful..." Like it's- it's, uh, it's amazing that something like this, something so simple can solve a problem like this?

   19. RKRichard Karp17:38

       Yeah. It's- it's really cool. If I had mechanical ability, I would probably like to do w- woodworking or other activities where you sort of shape something, uh, in- in- into something beautiful and orderly. And there's something about the orderly sys- systematic nature of, uh, that iterative algorithm that is pleasing to me.

   20. LFLex Fridman18:05

       So

5. 18:06 – 22:06

   Don Knuth and geeks

   1. LFLex Fridman18:06

      what do you think about this idea of geeks, as Don Knuth calls them? Uh, what do you think of- is it something, uh, specific to a mindset that allows you to-... discover the elegance in computational processes or is this all of us? Can all of us discover this beauty? Or, were, were you born this way? (laughs)

   2. RKRichard Karp18:28

      I think so. I always liked to play with numbers. I- I, uh, I used to amuse myself by multiplying four-digit decimal numbers in my head and putting myself to sleep by starting with one and doubling the number as long as I could go and testing my memory, my ability to retain the information.

   3. LFLex Fridman18:52

      And I also read somewhere that you, uh, you wrote that you enjoyed showing off to your friends by, I believe, multiplying four-digit numbers, uh-

   4. RKRichard Karp19:04

      Ri- right.

   5. LFLex Fridman19:05

      ... a couple of four-digit numbers.

   6. RKRichard Karp19:07

      Yeah. I had a summer job at a beach resort outside of Boston and, uh, the other employ- I was the barker at a Skee-Ball game.

   7. LFLex Fridman19:20

      Yeah.

   8. RKRichard Karp19:20

      I used to... sh- I used to sit at a microph- microphone saying, "Come one, come all, come in and play Skee-Ball. Five cents to play, a nickel to win," and so on.

   9. LFLex Fridman19:31

      That's what a barker-

   10. RKRichard Karp19:31

       Yeah.

   11. LFLex Fridman19:31

       I was gonna... I wasn't sure if I should know, but barker, that's... So you're the charming, outgoing person that's getting people to come in?

   12. RKRichard Karp19:41

       Yeah. Well, I wasn't particularly charming, but I could be very repetitious and loud. (laughs) And, um, the other employees were sort of ju- juvenile delinquents who had no academic bent, but somehow I found that I could impress them by, uh, by performing this mental mel- melt- mental arithmetic.

   13. LFLex Fridman20:06

       You know, there's something to that, that, you know, one of... S- some of the most popular videos on the internet is, um... There's a G- there's a YouTube channel called Numberphile that shows all different mathematical ideas.

   14. RKRichard Karp20:20

       I see.

   15. LFLex Fridman20:20

       There's still something really profoundly interesting to people about math.

   16. RKRichard Karp20:25

       Mm-hmm.

   17. LFLex Fridman20:26

       The beauty of it. Something... Even if they don't understand the basic concept even being discussed, there's something compelling to it. Wh- what do you think that is? Y- y- any lessons you drew from the early teen years when you were showing off (laughs) to your friends with the numbers?

   18. RKRichard Karp20:45

       (laughs)

   19. LFLex Fridman20:45

       Like is... What is it that attracts us to the beauty of mathematics do you think? The general population, not just the computer scientists and math, the mathematicians?

   20. RKRichard Karp20:56

       I think that it... You know, you can do amazing things. You can test whether large numbers are prime, you can, uh, um, you can solve little puzzles about can- cannibals and missionaries.

   21. LFLex Fridman21:12

       (laughs) Yeah.

   22. RKRichard Karp21:13

       And, uh, that's a kind of achievement. It's, it's puzzle solving. And at a higher level, the fact that you can, you can do this reasoning, that you can prove in an absolutely ironclad way that the sum of the angles of a triangle is 180 degrees.

   23. LFLex Fridman21:32

       Yeah. It's a nice escape from the messiness of the real world where nothing can be proved. So... And we'll talk about it, but sometimes the ability to map the real world into such problems where you can't prove it is a, is a powerful step.

   24. RKRichard Karp21:47

       Yeah.

   25. LFLex Fridman21:47

       It's amazing that we can do that.

   26. RKRichard Karp21:48

       Of course, another attribute of geeks is they- they're not necessarily, uh, endowed with emotional intelligence (laughs) and so they can live in a world of abstractions without having to master the complexities of dealing with people.

6. 22:06 – 25:53

   Early days of computers

   1. RKRichard Karp22:06

   2. LFLex Fridman22:06

      L- so j- just to link on a historical note, as a PhD student in 1955 you joined the computation lab at Harvard where Howard Aiken had built the Mark I and the Mark IV computers. Just take a step back into that history. What were those computers like?

   3. RKRichard Karp22:25

      Uh, the Mark IV filled a ma- a large room, much big- much bigger than this large office that we're-

   4. LFLex Fridman22:34

      Wow.

   5. RKRichard Karp22:34

      ... talking in now, and you could walk around inside it. There were, there were, uh, rows of relays. You could just walk around the interior and, uh, the... machine would sometimes fail, uh, because of bugs which literally meant flying creatures landing on the switches. Um, so I never, I never used that machine for any practical purpose. Um, we, the lab, eventually acquired a, uh... one of... one of the earlier, um, commercial computers.

   6. LFLex Fridman23:14

      This is already in the '60s?

   7. RKRichard Karp23:16

      No, in the mid '50s.

   8. LFLex Fridman23:17

      The mid '50s?

   9. RKRichard Karp23:18

      Or mi- late '50s.

   10. LFLex Fridman23:19

       There was already commercial-

   11. RKRichard Karp23:20

       UNIVAC.

   12. LFLex Fridman23:21

       ... computers in the-

   13. RKRichard Karp23:21

       Yeah. We had a UNIVAC, a 2000 UNIVAC with 2,000 words of storage.

   14. LFLex Fridman23:26

       Wow.

   15. RKRichard Karp23:27

       And so you had to work hard to allocate the s- the memory properly to... Also, the, uh, excess time from one word to another depended on the number of, uh, the particular words. And so you... uh, there was an art to sort of arranging the storage allocation to make fetching data rapid.

   16. LFLex Fridman23:51

       Were, were you attracted to this actual physical world implementation of mathematics? So it's a mathematical machine that's actually doing the math physically for you?

   17. RKRichard Karp24:03

       No. Not at all.

   18. LFLex Fridman24:04

       (laughs)

   19. RKRichard Karp24:04

       I think... (laughs) I was a- I was attracted to the underlying algorithms.

   20. LFLex Fridman24:10

       So... But did you draw any inspirations? So could you have imagined... Like, what did you imagine was the future of these giant computers? Could you have imagined that 60 years later we'd have billions of these computers all over the world?

   21. RKRichard Karp24:25

       I couldn't imagine that.But there was a sense in the laboratory that this was the wave of the future. In fact, my mother influenced me. She- she told me that data processing was gonna be really big and I should get into it.

   22. LFLex Fridman24:44

       (laughs)

   23. RKRichard Karp24:45

       Yeah.

   24. LFLex Fridman24:46

       She's a smart woman.

   25. RKRichard Karp24:47

       Yeah, she was a smart- a smart woman, and there was just a feeling that this was going to change the world, but I- I- I didn't think of it in terms of personal computing. I had no- I had no anticipation that we would be walking around with computers in our pockets or anything like that.

   26. LFLex Fridman25:06

       Did you see computers as tools, as mathematical mechanisms to analyze sort of through theoretical computer science or is the AI folks, which is an entire other community of dreamers-

   27. RKRichard Karp25:22

       Yeah.

   28. LFLex Fridman25:22

       ...uh, as something that could one day have human level intelligence?

   29. RKRichard Karp25:26

       Well, AI wasn't very much on my radar. I did read, uh, Turing's paper about the, uh, the, uh, sa- the, um-

   30. LFLex Fridman25:36

       The Turing test, computing and intelligence.
7. 25:53 – 30:05

   Turing Test

   1. RKRichard Karp25:53

      I didn't feel that the Turing test was really the right way to calibrate how intelligent a- an algorithm could be.

   2. LFLex Fridman26:00

      But to linger on that, do you think it's po- because you've come up with some incredible tests later on, tests on algorithms, right?

   3. RKRichard Karp26:09

      Yeah.

   4. LFLex Fridman26:09

      That are, uh, like strong, reliable, robust across a bunch of different classes of algorithms, but returning to this emotional mess that is intelligence-

   5. RKRichard Karp26:21

      Yeah.

   6. LFLex Fridman26:21

      ...do you think it's possible to come up with a test that's as ironclad as some of the computational complexity work?

   7. RKRichard Karp26:31

      Well, I think the greater question is whether it's possible to achieve human level- level intelligence.

   8. LFLex Fridman26:38

      Right, so that's- so first of all, let me, at the philosophical level, do you think it's possible to create algorithms that reason and would seem to us to have the same kind of intelligence as human beings?

   9. RKRichard Karp26:55

      It's an open question. Um, it seems to me that, um, most of the achievements have, uh, acquired, uh, operate within a very limited set of ground rules and for a very limited precise task, which is a quite different situation from the processes that go on in the minds of humans, which- where they have to sort of function in changing environments. They have emotions, they have, um, um, physical attributes for acquire- for exploring their environment. Um, they have intuition, they have desires, um, emotions, and I don't see anything in the current achievements of what's called AI that come close to that capability. I don't think there's any computer program which surpasses a six-month-old child in terms of comprehension of the world.

   10. LFLex Fridman28:10

       Do you think this complexity of human intelligence, all the cognitive abilities we have, all the emotion, do you think that could be reduced one day or just fundamentally, can it be reduced to an al- a set of algorithms or an algorithm? So can a Turing machine (laughs) achieve human level intelligence?

   11. RKRichard Karp28:33

       I am doubtful about that. I guess the argument in favor of it is that the human brain seems to achieve what we call intelligence, cognitive abilities of different kinds, and if you buy the premise that the human brain is just an enormous intricate- interconnected set of switches, so to speak, then in principle, you should be able to diagnose what that interconnection structure is like, characterize the individual switches and build a s- uh, simulation outside. But while that may be true in principle, that cannot be the way we're eventually gonna tackle this problem. It's, you know, (laughs) you know, that- that does not seem like a feasible way to go about it. So there is, however, an existence proof that, um, uh, if you believe that the brain is- is just a network of- of neurons operating by rules, I guess you could say that that's an existence proof of the ability to buil- uh, uh, the capabilities of a mechanism. Um, but it would be almost impossible to acquire the information unless we got enough insight into the operation of the brain.

   12. LFLex Fridman30:02

       But there's so much mystery there. Do you think...

8. 30:05 – 33:22

   Consciousness

   1. LFLex Fridman30:05

      Well, what do you make of consciousness, for example? Th- this something, as an example of something we completely have no clue about, the fact that we have this subjective experience.

   2. RKRichard Karp30:15

      Right.

   3. LFLex Fridman30:16

      Is it possible that this network of, uh, this circuit of switches is able to create something like consciousness?

   4. RKRichard Karp30:24

      To know- to know its own identity?

   5. LFLex Fridman30:26

      Yeah, to know- to know the algorithm to know itself. (laughs)

   6. RKRichard Karp30:30

      To know itself. (laughs) I think if you try to define that rigorously, you'd have a lot of trouble.

   7. LFLex Fridman30:36

      Yeah, that's easy. (laughs)

   8. RKRichard Karp30:38

      (laughs) So I know that there are, um, many who, um, believe that general intelligence can be achieved and there are even some who are... feel certain that, uh, uh, the singularity will come and, uh, we will be surpassed by the machines which will then learn more and more about themselves and reduce humans to an inferior breed. I am doubtful that this will ever be achieved.

   9. LFLex Fridman31:12

      Just for the fun of it, (laughs) could you linger on why, what's your intuition why you're doubtful? So there are quite a few people that are extremely worried-

   10. RKRichard Karp31:22

       Yeah.

   11. LFLex Fridman31:23

       ...about this, uh, existential threat of artificial intelligence, of us being left behind by these super intelligent new species. What's your intuition why that's not quite likely?

   12. RKRichard Karp31:37

       Just because, uh, none of the achievements in speech or robotics or, uh, natural language processing or creation of flexible computer assistants or any of that comes anywhere near close to that level of cognition.

   13. LFLex Fridman32:00

       What do you think about ideas of sort of, uh, if we look at Moore's Law-

   14. RKRichard Karp32:03

       Yeah.

   15. LFLex Fridman32:03

       ...and exponential improvement, uh, to allow us to... that would surprise us?

   16. RKRichard Karp32:09

       Right.

   17. LFLex Fridman32:09

       So does our intuition fall apart with, with exponential improvement because, I mean, we, we're not able to kind of... we kinda think in linear improvement.

   18. RKRichard Karp32:18

       Yeah.

   19. LFLex Fridman32:18

       We're not able to imagine a world that goes from the Mark I computer to a Sp- an iPhone X.

   20. RKRichard Karp32:26

       Yeah.

   21. LFLex Fridman32:27

       So do you think it would be... we could be really surprised by the exponential growth? Or, or on the flip side, is, is it possible that also intelligence is actually way, way, way, way harder, uh, even with exponential improvement, um, to be able to crack?

   22. RKRichard Karp32:47

       I don't think any constant factor improvement could-

   23. LFLex Fridman32:51

       (laughs)

   24. RKRichard Karp32:51

       (laughs) ...could change things. And given, given our current comprehension of how the... of, of, of what cognition requires, it seems to me that multiplying the speed of the switches by a factor of 1,000 or a million, uh, will not be useful until we really understand the organizational principle behind the, the network of switches.

9. 33:22 – 37:42

   Combinatorial algorithms

   1. RKRichard Karp33:23

   2. LFLex Fridman33:23

      Well, let's jump into the network of switches and talk about combinatorial algorithms, if we could. Let's step back with the very basics. What are combinatorial algorithms and what are some major examples of problems they aim to solve?

   3. RKRichard Karp33:38

      A combinatorial algorithm is, uh, is one which deals with a, um, a system of discrete objects that can, uh, occupy various states or take on various values from a discrete set of values, um, and need to be arranged or, or, um, uh, or selected, um, in such a way as to, uh, achieve some... to minimize some cost function, or to prove, or to s- prove the existence of some combinatorial configuration. So an example would be, um, coloring the vertices of a graph.

   4. LFLex Fridman34:25

      What's a graph? (laughs)

   5. RKRichard Karp34:27

      (laughs)

   6. LFLex Fridman34:27

      Let's step back. So what, uh... and it's fun to, uh, to ask one of the greatest computer scientists of all time the most basic questions in the beginning of most books. But for people who might not know, but in general, how you think about it, what is, what is a graph?

   7. RKRichard Karp34:44

      Uh, a graph, that's, that's simple. It's, it's a set of points, certain pairs of which are joined by lines called edges. And they sort of represent the... in different applications, represent the interconnections between, uh, discrete objects. So they could be the interactions, interconnections between switches in a digital circuit or interconnections indicating the communication patterns of a human community, um-

   8. LFLex Fridman35:19

      And they could be directed or undirected, and they, as you've mentioned before, might have costs on-

   9. RKRichard Karp35:25

      Right. They can be directed or undirected. They can be... you can think of them as, uh, if, if, if you think... if a graph were representing a communication network, then the edge could be undirected, meaning that information could flow along it in both directions, or it could be directed with only one-way communication. A road system is another example of a graph with weights on the edges. And then a lot of problems of, uh, optimizing the efficiency of such networks or learning about the performance of such networks, um, uh, are the s- are the object of combinatorial algorithms. So it could be, uh, scheduling classes at a school where, uh, the, uh, the, the vertices, the nodes of the network are the individual classes and, uh, the edges indicate the constraints which say that certain classes cannot take place at the same time or certain teachers are available only at cert- for certain classes, et cetera.Or, um, I talked earlier about the assignment problem of matching the boys with the girls, um, uh, where, um, you have, uh, there a graph with an edge from each boy to each girl, uh, with a weight indicating the cost. Or, um, in, uh, logical design of computers, you might want to find a set of so-called gates, switches that, that perform logical functions, which can be interconnected to realize some function. So you, you might ask, um, um, uh, "How many gates do you need in order to, um, um, for a, for a, um, circuit to give, uh, a yes output if at least a given number of its inputs are ones, and know if, uh, if few are, are present."

10. 37:42 – 40:22

    Edmonds-Karp algorithm

    1. RKRichard Karp37:43

    2. LFLex Fridman37:43

       My favorite is probably all the, all the work with network flow. So any time you have... Uh, I don't know why it's so compelling, but there's something just beautiful about it. It seems like there's so many applications and communication networks-

    3. RKRichard Karp37:56

       Mm-hmm.

    4. LFLex Fridman37:57

       ... uh, in, uh, traffic-

    5. RKRichard Karp37:59

       Right.

    6. LFLex Fridman38:00

       ... flow that you can map into these. And then you can think of pipes and water going through pipes, and you can optimize it in different ways. There's something c- always visually and in- intellectually compelling to me about it. And of course, you've done work there.

    7. RKRichard Karp38:15

       Yeah. Yeah. So, um, so there, uh, the edges represent, uh, channels along which some commodity can flow. It might be gas, it might be water, it might be information.

    8. LFLex Fridman38:29

       It could be supply chain as well, like products being delivered.

    9. RKRichard Karp38:33

       Products flowing from one operation to another.

    10. LFLex Fridman38:36

        Yeah.

    11. RKRichard Karp38:37

        And, uh, the edges have a capacity, which is the rate at which the commodity can flow. And, uh, a central problem is to determine, given a network of these channels, in, in this case, the edges are communication channels, um, the, uh, the challenge is to find the maximum rate at which the, uh, information can flow along these channels to get from a source to a destination. And, uh, that's a, that's a fundamental commentatorial problem that I, I've worked on, uh, jointly with, um, the scientist, Jack Edmonds. We, I think, were the first to give a formal proof that, uh, this maximum flow problem through a network, uh, can be solved in polynomial time.

    12. LFLex Fridman39:30

        Which, uh, I remember the first time I learned that, just learning that in, um, maybe even grad school. I don't think it was even undergrad. No, algorithm... Yeah. Do network, network flows get taught in, in, um, basic algorithms courses?

    13. RKRichard Karp39:50

        Yes, probably.

    14. LFLex Fridman39:51

        Okay. So yeah, I've, I remember being very surprised at max flow as a polynomial time algorithm.

    15. RKRichard Karp39:56

        Yeah.

    16. LFLex Fridman39:56

        That there's a nice fast algorithm that solves max flow. But... So there is an algorithm named after you and Edmonds, the Edmonds-Karp algorithm for max flow. So what was it like tackling that problem and trying to arrive at a polynomial time solution? And maybe you can describe the algorithm, maybe you can describe what's the running time complexity that you showed?

    17. RKRichard Karp40:20

        Yeah. Well,

11. 40:22 – 50:25

    Algorithmic complexity

    1. RKRichard Karp40:22

       uh, first of all, what is a polynomial time algorithm?

    2. LFLex Fridman40:25

       Yeah.

    3. RKRichard Karp40:25

       Perhaps we could discuss that.

    4. LFLex Fridman40:28

       So yeah, let's, let's actually just even... Yeah. That's... What is algorithm, uh, algorithmic complexity, and what are the major classes of algorithm complexity?

    5. RKRichard Karp40:38

       So we... In, in a problem like the assignment problem or, um, scheduling schools, or any of these applications, um, you have a set of input data which might, for example, be, um, um, uh, a set of vertices connected by edges with the in- you're given for each edge the capacity of the edge. And, um, you have, um, algorithms which are, uh, think of them as computer pro- programs with operations such as addition, subtraction, multiplication, division, comparison of numbers and so on. Um, and you're trying to construct an algorithm, uh, based on those operations which will determine in a minimum number of computational steps the answer to the problem. In this case, the computational step is one of those operations, and the answer to the problem is, let's say, the, um, the configuration of the network that carries the maximum amount of flow. And an algorithm is said to run in polynomial time if, as a function of the size of the input, the number of vertices, the number of edges and so on, um, the number of basic computational steps grows only as some fixed power of that size. A linear algorithm would execute a number of steps lineally proportional to the size. Quadratic algorithm would be steps proportional to the square of the size and so on. And algorithms that whose running time is bounded by some fixed power of the size are called polynomial algorithms. And-

    6. LFLex Fridman42:40

       And that's supposed to be-... relatively fast class of algorithms.

    7. RKRichard Karp42:44

       That's right. We theoreticians take that to be the definition of an algorithm being, um, efficient and a, uh, and we're interested in which problems can be solved by such efficient algorithms. One can argue whether that's the right definition of efficient, because you could have an algorithm whose running time is the 10,000th power of the size of the input and that wouldn't be really efficient. But-

    8. LFLex Fridman43:15

       And, and in practice it's oftentimes reducing from an N squared algorithm to an N log N or a linear time is practically the jump that you wanna make to allow a real world system to solve a problem.

    9. RKRichard Karp43:31

       Yeah, that's also true becau- especially as we get very large networks. The size can be in the millions and, uh, and then, uh, anything above, uh, N log N, where N is the size, would be, uh, too much for a practical solution.

    10. LFLex Fridman43:50

        Okay, so that's polynomial time algorithms. What other classes of algorithms are there? What's, so that usually they, they designate polynomials with a letter P.

    11. RKRichard Karp44:02

        Yeah.

    12. LFLex Fridman44:02

        There's also NP, NP-complete and NP-hard.

    13. RKRichard Karp44:06

        Yeah.

    14. LFLex Fridman44:07

        So can you try to disentangle those and s- by trying to define them simply?

    15. RKRichard Karp44:14

        Right, so a polynomial time algorithm is one which, whose running time is bounded by a polynomial and the size of the input. Uh, there's the, then there's the, the class of such algorithms is called P.

    16. LFLex Fridman44:29

        In the worst case, by the way, we should say, right?

    17. RKRichard Karp44:31

        Yeah, and, and yes, that's right.

    18. LFLex Fridman44:31

        So for every case of the problem.

    19. RKRichard Karp44:33

        And that's very important that in this theory, um, when we measure the complexity of an algorithm, we really measure the number of steps, the growth of the number of steps in the worst case. So you may have an algorithm that, um, runs very rapidly in most cases, but if there's any case where it gets into a very long computation, that would increase the computational complexity by this measure. And that's a very important issue because there, uh, as we may discuss later, there are some very important algorithms which don't have a good standing from the point of view of their worst case performance, and yet are very effective. So, so, uh, theoreticians are interested in P, the class of problems solvable in polynomial time. Then there's um, uh, NP, which is the class of problems which may be hard to solve, but where the, where, where when confronted with a solution, you can check it in polynomial time. Let me give you an example there. So if we look at the assignment problem. Uh, so you have uh, n boys, you have n girls, you, the number of numbers that you need to write down to specify the problem instances, n squared, and the question is, um, how many steps are needed to solve it? And, um, Jack Edmonds and I were the first to show that it could be done in time n cubed. Uh, earlier algorithms required n to the fourth. So as a polynomial function of the size of the input, this is a fast algorithm. Now, to illustrate the class NP, the question is how long would it take to, um, verify that a solution is optimal? So for example, if um, if the input was a graph, we might want to, um, find the largest clique in the graph, or a mo- a clique is a set of vertices such that any vertex, each vertex in the set is adjacent to each of the others. So the, uh, clique is a complete sub-graph.

    20. LFLex Fridman47:09

        Yeah, so if it's a Facebook social network, everybody's friends with everybody else, close clique of friends.

    21. RKRichard Karp47:15

        No, that would be what's called a complete graph. It would be...

    22. LFLex Fridman47:18

        No, I mean, uh, within that clique.

    23. RKRichard Karp47:20

        Uh, within that clique, yeah.

    24. LFLex Fridman47:22

        Yeah. (laughs)

    25. RKRichard Karp47:22

        Yeah, yeah. Every, uh, they're all friends.

    26. LFLex Fridman47:25

        So a complete graph is when, uh...

    27. RKRichard Karp47:27

        Everybody is friendly.

    28. LFLex Fridman47:28

        When everybody is friends with everybody, yeah.

    29. RKRichard Karp47:30

        Yeah. So the problem might be to, uh, determine whether in a given graph there exists a clique of a certain size. Well, that turns out to be a very hard problem. But how hard ... but if somebody hands you a clique and asks you to check whether it is a, uh, uh, hands you a set of vertices and asks you to check whether it's a clique, um, you could do that simply by exhaustively looking at all of the edges between the vertices and the clique, and verifying that they're all there.

    30. LFLex Fridman48:08

        And that's a polynomial time algorithm.
12. 50:25 – 54:25

    P=NP

    1. RKRichard Karp50:25

       So the theoretical question, which is considered to be the most central problem in theoretical computer science, or at least computational complexity theory, combinatorial algorithm theory, the question is whether P is equal to NP. If P were equal to NP, it would be amazing. It would mean that, um, every problem where a solution can be rapidly checked can actually be solved in polynomial time. We don't really believe that's true. If you're scheduling classes at a school, it's bl- uh, we e- expect that if somebody hands you a satisfying schedule, you can verify that it works. That doesn't mean that you should be able to find such a schedule. So intuitively, NP encompasses a lot more problems than P.

    2. LFLex Fridman51:24

       So can, uh, we take a small tangent and break apart that intuition? So do you, first of all, think that the biggest sort of open problem in computer science, maybe mathematics, is whether P equals NP? Do you think P equals NP or do you think P is not equal to NP? If you had to bet all your money on it. (laughs)

    3. RKRichard Karp51:48

       I w- I would bet that P is unequal to NP, uh, simply because there are problems that have been around for centuries and have been studied intensively in mathematics, and even more so in the last 50 years since the P versus NP was stated. And, um, no polynomial time algorithms have, have been found for these easy-to-check problems. So one e- one example is a problem that goes back to the mathematician Gauss, who was interested in, um, factoring large numbers. So, uh, we know what a pr- a number is prime if it doesn't h- if it cannot be written as the product of two or more numbers unequal to one. Uh, so if we can factor, uh, a number like 91, that's seven times 13. Um, but, uh, if I give you 20-digit or 30-digit numbers, you're probably gonna be at a loss to have any idea whether they can be factored. Um, so the pr- the problem of factoring very large numbers, uh, is, um, does not appear to have an efficient solution. But once you have found the factors, uh, uh, expressed the number as a product, the two smaller numbers, you can quickly verify that they are factors of the number.

    4. LFLex Fridman53:19

       And your intuition is a lot of people finding, you know, this... A lot of brilliant people have tried to find algorithms for this one particular problem. There's many others like it that are really well studied and would be great to find an efficient algorithm for.

    5. RKRichard Karp53:34

       Right. Eh, and in fact, um, we have, uh, some results that I was instrumental in obtaining, following up on work by the mathematician Steven Cook, um, to show that, uh, within the class NP of easy-to-check problems, there's a huge number that are equivalent in the sense that either all of them or none of them lie in P. And this happens only if P is equal to NP. So if P is unequal to NP, uh, we would also know that, uh, uh, virtually all the standard combinatorial problems, if, if P is unequal to NP, none of them can be solved in polynomial time.

13. 54:25 – 1:10:29

    NP-Complete problems

    1. RKRichard Karp54:25

    2. LFLex Fridman54:25

       Can you explain how that's possible to tie together so many problems in a nice bunch that if one is proven to be efficient, then all are?

    3. RKRichard Karp54:36

       The first, uh, and most important stage of progress was a result by, uh, Steven Cook, um......who showed that a certain problem called the satisfiability problem of propositional logic, uh, is as hard as any problem in the class P. So the propositional logic problem is expressed in terms of, um, expressions involving the logical operations and/or and not opering- opering- operating on, uh, variables that can be either true or false. So, uh, an instance of the problem would be some formula involving and/or and not. Um, and the question would be whether there is an assignment of truth values to the variables in the problem that would make the formula true. So for example, if I take, um, the formula A or B and A or not-B and not-A or B and not-A or not-B and take the conjunction of all four of those so-called expressions, you can determine that no s- assignment of truth values to the variables A and B, um, will allow that conjunction of cl- what are called clauses, uh, to be true. So that's an example of a formula in, um, propositional logic involving expressions, uh, based on the operations and/or and not. Um, that's an example of a problem which ha- which is not satisfiable. There is no solution that satisfies all of those constraints.

    4. LFLex Fridman56:31

       And that's like one of the cleanest and fundamental problems in computer science.

    5. RKRichard Karp56:35

       Right.

    6. LFLex Fridman56:35

       It's like a nice statement of a really hard problem.

    7. RKRichard Karp56:37

       It's a- it's a nice statement of a really hard problem. And- and what Cook showed is that, um, every problem in NP is- can be re-expressed as an instance of the satisfiability problem. So to do that, he, uh, used the observation that a very simple abstract machine called the Turing machine, um, can be used to describe any algorithm, uh, uh, uh, uh, uh, an algorithm for any realistic computer can be translated into, uh, an equivalent algorithm on, uh, one of these, uh, Turing machines which are extremely simple.

    8. LFLex Fridman57:28

       So a Turing machine is a tape and you can-

    9. RKRichard Karp57:30

       Yeah, you- you have-

    10. LFLex Fridman57:31

        ...walk along that tape.

    11. RKRichard Karp57:32

        ...data on a tape and you have basic instructions, uh, a finite list of instructions which say- wh- which say if you're reading a particular symbol on the tape, um, and you're in a particular state, then you can move to, um, a different state and change the state of the number that you- or the element that you were looking at, the cell of the tape that you were looking at.

    12. LFLex Fridman57:55

        And that was like a metaphor and a mathematical construct that Turing put together to represent all possible computation.

    13. RKRichard Karp58:02

        All possible computation. Now one of these so-called Turing machines is too simple to be useful in practice, but for theoretical purposes, we can depend on the fact that an algorithm for any computer can be translated into one that would run on a Turing machine.

    14. LFLex Fridman58:21

        Right.

    15. RKRichard Karp58:22

        Uh, and then using that fact, um, he could sort of describe, um, any possible non-deterministic polynomial time algorithm, any pro- any algorithm for a problem in NP could be expressed as a sequence of, uh, moves of the Turing machine, uh, described in terms of reading a symbol on the tape, um, while you're in a given state and moving to a new state and leaving behind a new sy- new symbol. And given that, uh, the fact that any non-deterministic polynomial time algorithm can be described by a list of such instructions, you could translate the problem into the language of the satisfiability problem.

    16. LFLex Fridman59:19

        Is that amazing to you, by the way? If you take yourself back when you were first thinking about this space of problems. Is that... How amazing is that?

    17. RKRichard Karp59:26

        It's- it's astonishing. When you look at Cook's proof, it's not too difficult to sort of figure out why this is- why this is so, but the implications are staggering. It- it tells us that this- of all the problems in NP, all the problems where solutions are easy to check, uh, they can a- they can all be rewritten in terms of, uh, the satisfiability problem.

    18. LFLex Fridman59:59

        Yeah, it's a- in adding so much more weight to the P equals NP question, because all it takes is to show that one-

    19. RKRichard Karp1:00:09

        That's right. So-

    20. LFLex Fridman1:00:09

        ...one algorithm in this class-

    21. RKRichard Karp1:00:11

        So the P versus NP can be re-expressed as- as simply asking whether the satisfiability problem of propositional logic is solvable in polynomial time. But there's more. Um, uh, I- I encountered Cook's paper when he published it in a conference in 1971. Yeah, so when I saw, uh, Cook's paper and saw this, uh, reduction of en- of all- of each of the problems in NP by a uniform method to- to the satisfiability problem of propositional logic, I-That meant that the satisfiability problem was a universal combinatorial problem. And it occurred to me through experience I had had in trying to solve other combinatorial problems, that there were many other problems which seemed to have that universal structure. And so I began looking for reductions from the satisfiability to other problems. Um, uh, one of the other problems would be, uh, the so-called integer programming problem of, um, solving a, determining whether there's a solution to a, um, a set of linear inequalities involving integer variables.

    22. LFLex Fridman1:01:48

        Just like linear programming, but there's a constraint that-

    23. RKRichard Karp1:01:51

        Mm-hmm.

    24. LFLex Fridman1:01:51

        ... the variables must-

    25. RKRichard Karp1:01:52

        Be-

    26. LFLex Fridman1:01:52

        ... remain integers?

    27. RKRichard Karp1:01:53

        Integers, in fact, must be the zero or one. Could take on, could only take on those values.

    28. LFLex Fridman1:01:58

        And that makes the problem much harder?

    29. RKRichard Karp1:02:00

        Yes, that makes the problem much harder. And, um, it was not difficult to show that the satisfiability problem can be restated as an integer programming problem.

    30. LFLex Fridman1:02:13

        So can you pause on that? Was that one of the first pro- mappings that you tried to do?
14. 1:10:29 – 1:12:57

    Proving P=NP

    1. LFLex Fridman1:10:30

       So if somebody shows that P equals NP, what do you think that proof will look like if you were to put on your sort of ... (laughs) I- if it's possible to show that as a proof or to demonstrate an algorithm.

    2. RKRichard Karp1:10:49

       All I can say is that it will involve concepts that we do not now have and approaches that we don't have. Uh-

    3. LFLex Fridman1:10:56

       Do you think those concepts are out there in terms of inside complexity theory, inside of computational analysis of algorithms? Do you think there's concepts that are totally outside of the box that we haven't considered yet?

    4. RKRichard Karp1:11:09

       I think that if there is a proof that P is equal to NP or that P is unequal to NP, uh, it'll depend on concepts that are now outside the box.

    5. LFLex Fridman1:11:22

       Now, if that's shown, either way, P equals NP or P not ... Well, actually, P equals NP, what impact ... You kind of mentioned a little bit, but can you, can you linger on it? What kind of impact would it have on theoretical computer science and perhaps software-

    6. RKRichard Karp1:11:40

       Well, I-

    7. LFLex Fridman1:11:40

       ... uh, systems in general?

    8. RKRichard Karp1:11:42

       Well, I think it would have enormous impact on the, on the world any, in either way case. If P is unequal to NP, which is what we expect, then we know that we're i- that for the great majority of the combinatorial problems that come up, since they are known to be NP-complete, uh, we're not going to be able to solve them by efficient algorithms. However, there's a little bit of hope in that it may be that we can solve most instances. All we know is that if a problem's not in P, then, th- then it can't be solved efficiently on all instances. Um, but, but basically it will, um, it will, if we find that P is unequal to NP, it will mean that we can't ex- expect always to get the optimal solutions to these problems. And we have to depend on heuristics that perhaps work most of the time or give us good approximate solutions, but not, uh-

    9. LFLex Fridman1:12:48

       So, so we would turn our eye towards the heuristics-

    10. RKRichard Karp1:12:51

        We would-

    11. LFLex Fridman1:12:52

        ... w- w- with a little bit more, um, acceptance and comfort in our hearts.

    12. RKRichard Karp1:12:56

        Exactly.

15. 1:12:57 – 1:20:32

    Stable marriage problem

    1. RKRichard Karp1:12:57

    2. LFLex Fridman1:12:57

       Okay, so let me ask a romanticized question. (laughs) What to you is one of the most or the most beautiful combinatorial algorithm?In your own life or just in general in the field that you've ever come across or have developed yourself?

    3. RKRichard Karp1:13:14

       Uh, I like the stable matching problem or the stable marriage problem, uh, very much.

    4. LFLex Fridman1:13:22

       Wha- what's the stable matching problem?

    5. RKRichard Karp1:13:25

       Mm. Yeah. Imagine that you want to marry off n boys with, uh, n girls, and each boy has an ordered list of his preferences among the girls, his first choice, his second choice, through her nth choice. And, um, each girl also has a, an ordering of the boys as first choice, second choice, and so on. And we'll say, uh, and we, we'll say that a matching, uh, uh, one-to-one matching of the boys with the girls is stable if there are no two couples in the matching such that the boy in the first couple prefers the girl in the second couple to her mate and she prefers the boy to her current mate. In other words, if there is m- the matching is stable if there is no pair who want to run away with each other, leaving their partners behind.

    6. LFLex Fridman1:14:38

       Gotcha. (laughs) Uh, yeah.

    7. RKRichard Karp1:14:44

       It, actually this is relevant to, uh, matching, uh, uh, residents with hospitals and some other real-life problems, although, uh, not quite in the form that I described. So it turns out that there is but a stable... For any set of preferences, a stable matching exists, and, um, moreover, it can be computed by a simple algorithm in which, um, each boy starts making proposals to girls. And if a girl receives a proposal, she accepts it tentatively, but she can drop it if... She can end it, she can drop it later if she gets a better proposal from her point of view. And the boys start going down their lists proposing to their first, second, third choices until, uh, you know, stopping when a, a proposal is accepted. Uh, but the girls meanwhile are watching the proposals that are coming in to them, and the girl will drop her current partner, um, if, uh, she gets a better proposal.

    8. LFLex Fridman1:16:03

       And the, the boys never go back through the list.

    9. RKRichard Karp1:16:06

       They, they never go back, yeah. So once they've been denied- (laughs)

    10. LFLex Fridman1:16:11

        (laughs) They don't try again.

    11. RKRichard Karp1:16:12

        They don't, they don't, they don't try again because, uh, the girls are always improving their status as they get more, as they receive-

    12. LFLex Fridman1:16:21

        Right.

    13. RKRichard Karp1:16:21

        ... better and better proposals. The boys are going down their list starting with their top preferences. And, um, one can prove that, uh, uh, that the process will come to an end where everybody will get matched with somebody and you'll, you won't have any pair that want to abscon- abscond from each other.

    14. LFLex Fridman1:16:50

        Do you find the proof or the algorithm itself beautiful or is it the fact that with the s- the simplicity of just the two marching... I mean, the simplicity of the underlying rule of the algorithm, is that the beautiful part?

    15. RKRichard Karp1:17:04

        Both I, I would say. Um, and you also have the observation that, uh, you might ask, uh, who is better off, the boys who are doing the proposing or the girls who are reacting to proposals? And it turns out that it- it's the boys who are doing the, doing the best. That is, each boy is doing at least as well as, uh, he could do in any other stable matching. So there's a sort of lesson for the boys that you should go out and be proactive and make those proposals, go, go for broke.

    16. LFLex Fridman1:17:39

        (laughs) Uh, I don't, I don't know if the, this is directly mappable philosophically to our society, but, uh, certainly seems like a compelling notion. And, uh, uh, like you said, there's probably a lot of actual real world problems that this could be mapped to.

    17. RKRichard Karp1:17:54

        Yeah. Well, you get, you, you get, uh, complications. For example, what happens when a husband and wife want to be assigned to the same hospital? So you, uh, you, you have to take those constraints into account. Uh, and then the problem becomes NP-hard or... (laughs)

    18. LFLex Fridman1:18:15

        Uh, why, why is it a problem for the husband and wife to be assigned to the same hospital?

    19. RKRichard Karp1:18:20

        No. Uh, it's desirable-

    20. LFLex Fridman1:18:21

        Desirable.

    21. RKRichard Karp1:18:21

        ... so that... Or at least go to the same city. So you can't, uh, if you're-

    22. LFLex Fridman1:18:26

        I see.

    23. RKRichard Karp1:18:27

        ... if you're assigning residents to hospitals.

    24. LFLex Fridman1:18:29

        And then you have some preferences, uh, for the, the husband and the wife or for the hospitals?

    25. RKRichard Karp1:18:34

        The residents have their own preferences. References, residents both male and female have their own preferences. Um, the hospitals have their preferences. But if, if, uh, resident A, the boy is going to Philadelphia, then you'd like his wife, uh, be als- also to be assigned to a hospital in Philadelphia, so-

    26. LFLex Fridman1:19:04

        Which step makes it a NP-hard problem that you mentioned?

    27. RKRichard Karp1:19:08

        The fact that you have this additional constraint, that it's not just the preferences of individuals but the fact that the...... two partners to a marriage have to go, have to be assigned to the same place.

    28. LFLex Fridman1:19:22

        I'm being a little dense, uh, the wha- uh, sort of, the perfect matching? No, not the perf- stable matching-

    29. RKRichard Karp1:19:32

        Yeah.

    30. LFLex Fridman1:19:32

        ... is what you refer to. That's when two partners are trying to-
16. 1:20:32 – 1:33:23

    Randomized algorithms

    1. LFLex Fridman1:20:32

       So you've also have developed yourself some elegant, beautiful algorithms. Again, picking your children, so the, the, the Rabin-Karp algorithm for string searching, pattern matching, Edmond-Karp algorithm for max flows we mentioned, Hopcroft-Karp algorithm for finding maximum cardinality matchings in bipartite graphs. Is there ones that stand out to you as ones you're most proud of or just, um, whether its beauty, elegance, or just being the right discovery, development in your life that you're especially proud of?

    2. RKRichard Karp1:21:10

       I like the Rabin-Karp algorithm because it illustrates the power of randomization. So, um, the, the problem there is to, um, is to, uh, decide whether, uh, a given long string of symbols from some alphabet contains a given word, whether a particular word occurs within some very much longer word. And so the, the idea of the, um, algorithm is to associate with the word that we're looking for, a fingerprint-

    3. LFLex Fridman1:21:58

       Mm-hmm.

    4. RKRichard Karp1:22:00

       ... some, some number or some combinatorial object that describes that word, and then to look for an occurrence of that same fingerprint as you slide along the longer word. And what we do is we aso- associate with each word, a number. So we first of all, we think of the letters that are gonna occur in a word as the digits of, let's say, decimal or whatever base here, whatever number of different symbols there are in, in the alphabet.

    5. LFLex Fridman1:22:42

       That's the base of the, of the numbers, yeah.

    6. RKRichard Karp1:22:44

       Right. So every word can then be thought of as a number with the letters being the digits of that number.

    7. LFLex Fridman1:22:52

       Mm-hmm.

    8. RKRichard Karp1:22:53

       And then we pick a random prime number in a certain range, and we take that word viewed as a number and take the remainder on dividing the, dividing that number by the prime.

    9. LFLex Fridman1:23:12

       So coming up with a nice hash function.

    10. RKRichard Karp1:23:14

        It's a, it's a kind of hash function.

    11. LFLex Fridman1:23:16

        Yeah.

    12. RKRichard Karp1:23:17

        Um-

    13. LFLex Fridman1:23:18

        It gives you a little, little shortcut for, for that particular word.

    14. RKRichard Karp1:23:22

        Yeah. That, so that's the, that's the, um-

    15. LFLex Fridman1:23:26

        It's very different than the, any, uh, and other algorithms of its kind that were trying to do search, uh, um, string matching.

    16. RKRichard Karp1:23:35

        Yeah.

    17. LFLex Fridman1:23:36

        Right?

    18. RKRichard Karp1:23:36

        Which, uh, usually are combinatorial and don't involve the idea of taking a random fingerprint.

    19. LFLex Fridman1:23:42

        Yes.

    20. RKRichard Karp1:23:43

        And doing the fingerprinting has two advantages. One is that as we slide along the long word digit by digit, we can, we, we keep a window of, of a certain size, the size of the word we're looking for, and we loo- we compute the fingerprint of every se- stretch of that length. And it turns out that just a couple of arithmetical op- operations will take you from the fingerprint of one part to what you get when you slide over by one position. So the computation of all the fingerprints is, um, simple. And se- and secondly, it's unlikely if the prime is chosen randomly from a certain range that you will get two of the segments in question having the same fingerprint.

    21. LFLex Fridman1:24:41

        Right.

    22. RKRichard Karp1:24:41

        And so there's a small probability of error which can be checked after the fact, and also the ease of doing the computation because you're working with these fingerprints, which are remainders modulo, some big prime.

    23. LFLex Fridman1:24:55

        So that's the magical thing about randomized algorithms is that if you add a little bit of, uh, randomness it somehow allows you to take a pretty naive approach, a simple-looking approach, and allow it to run extremely well. Uh, so can you maybe take a step back and say, like, what is a randomized algorithm, this category of algorithms?

    24. RKRichard Karp1:25:18

        Well, it's, um, just the ability to draw a random number from such, um-... from some range or to, uh, to associate a random number with some object, or to draw fr- at random from some set. So, uh, another example is, um, very simple. If we're conducting a presidential election and, uh, we would like to pick the winner, um, in principle, we could draw a random sample of all of the voters in the country and if it was a si- of substantial size, say a few thousand, then the most popular candidate in that group would be very likely to be the correct choice that would come out of counting all the millions of votes. Uh, now of course we can't do this because first of all, everybody has to feel that his or her vote counted, and secondly, we can't really do a purely random sample from that population. And I guess thirdly, there could be a tie in which case, um, we wouldn't have a significant difference between two candidates. Mm-hmm.

    25. LFLex Fridman1:26:36

        But those things aside, if you didn't have all that messiness of human beings, you could prove that that kind of random picking would come up with-

    26. RKRichard Karp1:26:43

        Just that random picking would, would be, uh, would solve the problem with a very, with a very low probability of error. Another example is, um, testing whether a number is prime. So if I wanna test whether, uh, 17 is prime, I could pick, uh, an- any number between one and 17-

    27. LFLex Fridman1:27:08

        Mm-hmm.

    28. RKRichard Karp1:27:08

        ...and raise it to the 16th power, modulo 17, and it sh- and you should get back the original number. That's a famous, uh, formula due to Fermat about... Uh, it's called Fermat's Little Theorem that, um, if you take any A, any number A in the range, uh, zero through N minus one, and raise it to the N minus 1th pa- uh, power, modulo N, you'll get back the number A.

    29. LFLex Fridman1:27:40

        Okay.

    30. RKRichard Karp1:27:41

        If the number is... If A is prime.
17. 1:33:23 – 1:43:57

    Can a hard problem be easy in practice?

    1. LFLex Fridman1:33:23

       so we, we've just talked about randomized algorithms, but we can look at the probabilistic analysis of algorithms. And that, that gives us an opportunity to step back and as we've said, everything we've been talking about is worst case analysis.

    2. RKRichard Karp1:33:37

       Right.

    3. LFLex Fridman1:33:38

       Could you maybe comment on the usefulness and the power of worst case analysis versus best case analysis, average case, probabilistic? Eh, how do we think about the future of theoretical computer science, computer science in the kind of analysis we do of algorithms? Does worst case analysis still have a place, an important place? Or do we want to try to move forward towards kind of average case analysis?

    4. RKRichard Karp1:34:06

       Yeah.

    5. LFLex Fridman1:34:07

       And what, what are the challenges there?

    6. RKRichard Karp1:34:09

       So if worst case analysis shows that a, uh, an algorithm is always good, that, that's fine. Uh, if worst case analysis, uh, is used to show that the problem that the solution is not always good, then you have to step back and do something else to, to ask, how often will you get a good solution?

    7. LFLex Fridman1:34:35

       Just, just to pause on that for a second. That, that's so beautifully put, because I think we tend to judge algorithms. We throw them in the trash the moment their sh- their worst case is shown to be bad.

    8. RKRichard Karp1:34:48

       Right. And, and, and that's unfortunate. I think we, um, uh, a good example is, um, going back to the satisfiability problem. Um, there are very powerful programs called SAT solvers, which in practice fairly reliably solve instances with many millions of variables that arise in digital design or in proving programs correct and other applications. Um, and so, uh, in, in many application areas, even though satisfiability, as we've already discussed, is NP-complete, um, the SAT solvers will work so well that the people in that discipline tend to think of satisfiability as an easy problem.

    9. LFLex Fridman1:35:40

       Mm.

    10. RKRichard Karp1:35:41

        So you know, where it's just for some reason that we don't entirely understand, the instances that people formulate in designing digital circuits or other applications are such that, um, satisfiability is not hard to check. And even searching for a satisfying solution can be done efficiently in practice. And there are many examples. For example, um, we talked about the traveling salesman problem. So just to refresh our memories, uh, the problem is that you've got a set of cities. You have pairwise distances between cities, um, and you want to find a tour through all the cities that minimizes the total ch- the total cost of all the edges traversed, all the, all the trips between cities. The problem is NP-hard, but people using integer programming codes toget- together with some other mathematical tricks, uh, can solve geometric instances of the problem where the cities are, let's say, points in the plane, uh, and get optimal solutions to problems with tens of thousands of cities. Actually, it'll take a few computer months to solve a problem of that size, but for problems of size 1,000 or two, it'll rapidly get optimal solutions, provably optimal solutions, uh, even though again, we know that it's unlikely it a- that the t- traveling salesman problem can be solved in polynomial time.

    11. LFLex Fridman1:37:28

        Are there methodologies like rigorous systematic methodologies for...You said in practice.

    12. RKRichard Karp1:37:38

        Yeah.

    13. LFLex Fridman1:37:38

        In practice, this algorithm runs pretty good. Are there systematic ways of saying, "In practice this runs pretty good." So, in other words, average case analysis. Or you've also mentioned that average case kind of requires you to understand what the typical case is, typical instance is.

    14. RKRichard Karp1:37:53

        Yeah.

    15. LFLex Fridman1:37:53

        And that might be really difficult.

    16. RKRichard Karp1:37:55

        That's very difficult. So after I did my original work, uh, on, uh, getting, uh, showing all these problems through the NP-complete, I looked around for a way to get some, shed some positive light on combinatorial algorithms. And what I tried to do was to study, um, uh, problems, uh, behavior on the average or with high probability. But I had to make some assumptions about what, what, what's the probability space, what's the sample space, what are the, what do we mean by typical problems? That's very hard to say. So I took the easy way out and made some very simplistic assumptions. So I assumed, for example, that if we were generating a graph with a certain number of vertices and edges, then we would generate the graph by simply choosing one edge at a time at ran- at random until we got the right number of edges. That's, that's a particular model of random graphs that has been studied mathematically a lot. And within that model, I, I could prove all kinds of wonderful things, I and others who also worked on this. Uh, so we could show that we know exactly how many edges there have to be in order for, um, there to be a, a so-called Hamiltonian circuit, that's a, a cycle that visits each vertex exactly once. Um, we know that if the, uh, number of edges is a little bit more than N log N, where N is the number of vertices, then where such a cycle is very likely to exist, and we can give a heuristic that will find it with high probability. And we got a, uh, the community, um, in which I was working got a lot of results along these lines. Um, but the field tended to be rather lukewarm about accepting these results as meaningful, because we were making such a simplistic assumption about the kinds of graphs that we would be dealing with. So we could show all kinds of wonderful things. It was a great playground. I enjoyed doing it, but after a while I concluded that, um, um, that, um, it didn't have a lot of bite in terms of the practical application.

    17. LFLex Fridman1:40:31

        Of the... Okay, so it's too much into the world of toy problems.

    18. RKRichard Karp1:40:35

        Yeah.

    19. LFLex Fridman1:40:35

        That can... Okay. But, all right, but is, is there a way to find nice representative real world impactful instances of a problem on which to demonstrate that an algorithm is good? So this is kind of like, the machine learning world, that's kind of what they, at its best tries to do, is find a dataset-

    20. RKRichard Karp1:40:56

        Mm-hmm.

    21. LFLex Fridman1:40:56

        ... from like the real world-

    22. RKRichard Karp1:40:57

        Yeah.

    23. LFLex Fridman1:40:57

        ... and show the performance, all the, all the conferences are all focused on beating the performance of, on that real world dataset.

    24. RKRichard Karp1:41:07

        Yeah.

    25. LFLex Fridman1:41:07

        Is there an equivalent in complexity analysis?

    26. RKRichard Karp1:41:11

        Not really. Um, D- Don Knuth, uh, started to collect examples of graphs coming from various places. So he would have a whole zoo of different graphs that he could choose from and he could, could study the performance of algorithms on different types of graphs. And, um-

    27. LFLex Fridman1:41:33

        But there, it's really important and, and compelling to be able to define a class of graphs. So, (laughs) the, the, the actual act of defining a class of graphs that you're interested in, it seems to be, um, a non-trivial step if we're talking about instances that we should care about in the real world.

    28. RKRichard Karp1:41:51

        Yeah. It's, uh, there's nothing available there that would be analogous to the training set for supervised learning, you know, where you sort of assume that, uh, the, the world has given you a bunch of, uh, examples, uh, to work with. Uh, we, we don't really have that for problems, uh, for combinatorial problems on graphs and networks.

    29. LFLex Fridman1:42:18

        You know, there's been a, a huge growth, a big growth of datasets-

    30. RKRichard Karp1:42:22

        Yeah.
18. 1:43:57 – 1:46:21

    Open problems in theoretical computer science

    1. LFLex Fridman1:43:57

       So let me ask in terms of breakthroughs and open problems, what are the most compelling open problems to you and what possible breakthroughs do you see in the near term in terms of th- theoretical computer science?

    2. RKRichard Karp1:44:13

       Well, there are all kinds of relationships among complexity classes that can be studied. Um, just to mention one thing, I w- wrote a paper with, uh, Richard Lipton in, in 1979 where we asked the following question, um... If you take a probl- a, a combinatorial problem in NP, let's say, and you, um, choose a, uh, and you pick a, a, a, the, the size of the problem, uh, say, uh, it's a traveling salesman problem but of size 52 and you ask, uh, uh, "Could you get an efficient, a small Boolean circuit tailored for that size, 52, where you could feed the edges of the graph in, in as Boolean inputs and get as an output the question of whether or not there's a tour of a certain length?" And that would, in other words, briefly what you would say in that case is that the problem has small circuits, polynomial-sized circuits. Now, we know that if P is equal to NP, then in fact these problems will have small circuits. But what about the converse? Could a problem have small circuits, meaning that it's, that an algorithm tailored to any particular size could work well and yet not be a polynomial time algorithm? That is, you couldn't write it as a single uniform algorithm good for all sizes.

    3. LFLex Fridman1:45:57

       Just to clarify, small circuits for a problem of particular size or even further constraint, small circuit for a particular-

    4. RKRichard Karp1:46:07

       For a... No, for all the inputs of that size.

    5. LFLex Fridman1:46:09

       Of that size. Is that a trivial problem for a particular instance of... So coming up, an automated way of coming up with a circuit. I guess that's just gonna be-

    6. RKRichard Karp1:46:19

       That would be, that would be, that would be hard, yeah.

19. 1:46:21 – 1:50:49

    A strange idea in complexity theory

    1. RKRichard Karp1:46:21

    2. LFLex Fridman1:46:21

       Yeah.

    3. RKRichard Karp1:46:22

       But, you know, but there's the existential question. Everybody talks nowadays about every, existential questions. (laughs)

    4. LFLex Fridman1:46:31

       (laughs)

    5. RKRichard Karp1:46:31

       Uh, ex- existential challenges.

    6. LFLex Fridman1:46:33

       Yeah. (laughs)

    7. RKRichard Karp1:46:35

       Um, um, you could ask th- the question, um, does the Hamiltonian circuit problem have, uh, a small circuit for, for every size, for each size a different small circuit? In other words, could you tailor solutions depending on the size and, and get polynomial size?

    8. LFLex Fridman1:47:00

       Even if P is not equal to NP?

    9. RKRichard Karp1:47:02

       Right. And what-

    10. LFLex Fridman1:47:06

        That would be fascinating if that's true.

    11. RKRichard Karp1:47:08

        Yeah. What we proved is that if that were possible, then something strange would happen in complexity theory. (laughs)

    12. LFLex Fridman1:47:19

        (laughs)

    13. RKRichard Karp1:47:19

        Some high l- high level, uh, class which I could briefly describe. Um, something strange would happen. So, um, I'll take a stab at describing what I mean by this class.

    14. LFLex Fridman1:47:32

        Sure. Let- let's go there.

    15. RKRichard Karp1:47:34

        So we have to define this hierarchy in which the first level of the hierarchy is P and the second level is NP. And what is NP? NP involves statements of the form there exists a something such that something holds. Um, so, uh, uh, for example, um, um, there exists a coloring such that a graph can be colored with only that number of colors or there exists a Hamiltonian circuit.

    16. LFLex Fridman1:48:09

        There's a statement about this graph.

    17. RKRichard Karp1:48:10

        Yeah. So, so the, um, NP, um... N- NP deals with statements of that kind, that there exists a solution. Now you could imagine, uh, a more complicated, uh, f- expression which, which says, um, uh, for all X there exists a Y such that some, uh, proposition holds involving both X and Y. So that would say, for example, in game theory, for all, um, strategies for the first player, there exists a strategy for the second player such that the first player wins. That would be, that would be at the second level of the hierarchy. The third level would be there exists an A such that for all B there exists a C that something holds, and you can imagine going higher and higher in the hierarchy. And you'd expect that the cla- the complexity clas- classes that correspond to those different cases would get bigger and bigger. Or they, they, they-

    18. LFLex Fridman1:49:27

        What do you mean by bigger and bigger?

    19. RKRichard Karp1:49:28

        Sorry. Sorry. They, they'd get harder and harder to solve.

    20. LFLex Fridman1:49:30

        Harder and harder, right.

    21. RKRichard Karp1:49:31

        Harder and hard- harder and harder to solve. And what R- Lipton and I showed was that if, um, NP had small circuits, then this hierarchy would collapse down to the second level.

    22. LFLex Fridman1:49:45

        Hmm.

    23. RKRichard Karp1:49:46

        In other words, you wouldn't get any more mileage by complicating your expressions with three quantifiers or four quantifiers or any number.

Episode duration: 2:07:32