#111 – Richard Karp: Algorithms and Computational Complexity

Richard Karp is 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 Edmonds–Karp algorithm for solving the maximum 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 vs NP problem. Support this podcast by supporting our sponsors: – Eight Sleep: https://eightsleep.com/lex – Cash App – use code “LexPodcast” and download: – Cash App (App Store): https://apple.co/2sPrUHe – Cash App (Google Play): https://bit.ly/2MlvP5w If you would like to get more information about this podcast go to https://lexfridman.com/ai or connect with @lexfridman on Twitter https://twitter.com/lexfridman, LinkedIn https://www.linkedin.com/in/lexfridman/, Facebook https://www.facebook.com/lexfridman, Medium https://medium.com/@lexfridman, or YouTube https://www.youtube.com/lexfridman where you can watch the video versions of these conversations. If you enjoy the podcast, please rate it 5 stars on Apple Podcasts https://podcasts.apple.com/us/podcast/artificial-intelligence/id1434243584, follow on Spotify https://open.spotify.com/show/2MAi0BvDc6GTFvKFPXnkCL, or support it on Patreon https://www.patreon.com/lexfridman. Here’s the outline of the episode. On some podcast players you should be able to click the timestamp to jump to that time. OUTLINE: 00:00 – Introduction 03:50 – Geometry 09:46 – Visualizing an algorithm 13:00 – A beautiful algorithm 18:06 – Don Knuth and geeks 22:06 – Early days of computers 25:53 – Turing Test 30:05 – Consciousness 33:22 – Combinatorial algorithms 37:42 – Edmonds-Karp algorithm 40:22 – Algorithmic complexity 50:25 – P=NP 54:25 – NP-Complete problems 1:10:29 – Proving P=NP 1:12:57 – Stable marriage problem 1:20:32 – Randomized algorithms 1:33:23 – Can a hard problem be easy in practice? 1:43:57 – Open problems in theoretical computer science 1:46:21 – A strange idea in complexity theory 1:50:49 – Machine learning 1:56:26 – Bioinformatics 2:00:37 – Memory of Richard’s father

Speaker names marked ? are inferred from speaking time and the show’s known hosts — they are not voice-verified.

• 0:00Lex Fridman?

  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 Admiral's Karp algorithm for solving the Max flow problem on networks, Hopcraft Karp algorithm for finding maximum cardinality matchings in bipartite graphs, and his landmark paper in complexity theory called Reducability 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

• 0:43Lex Fridman?

  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 and up a podcast, support it on Patreon, or connect with me on Twitter at @LexFriedman. 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 PodPro mattress that you can check out

• 1:28Lex Fridman?

  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 and 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 of 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.

• 2:13Lex Fridman?

  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 8Sleep Pod Pro mattress. Check it out at 8sleep.com/lex to get $200 off. And remember, just visiting the site and considering the purchase helps convince the folks at 8Sleep 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.

• 2:58Lex Fridman?

  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, a 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

• 3:42Lex Fridman?

  and STEM education for young people around the world. And now, here's my conversation with Richard Karp.

• 4:07Lex Fridman?

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

• 4:30Speaker 01

  So Michael Rayburn told me this story. About an experience he had when he was a young student, who was 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 said, 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

• 5:15Speaker 01

  distance between the two centers. And any other line connecting the circles would be 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.

• 5:34Lex Fridman?

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

• 5:46Speaker 01

  Well, any, any segment joining the two circles, if you extend it by taking the radius on each side, you get a segment with, 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.

• 6:10Lex Fridman?

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

• 6:21Speaker 01

  Well, just that you could establish a fact about geometry.

• 6:29Speaker 01

  Beyond dispute by pure reasoning. I also enjoy 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.

• 6:49Lex Fridman?

  Was there something about geometry itself, the slightly visual component of it?

• 6:55Speaker 01

  Oh, yes, absolutely. Although I lacked three dimensional vision. I wasn't very good at three dimensional vision.

• 7:04Lex Fridman?

  You mean being able to visualize three dimensional objects?

• 7:06Speaker 01

  Three dimensional objects or surfaces, hyperplanes and so on.

• 7:14Speaker 01

  So there I didn't have an intuition. But, for example, the fact that the sum of the angles of a triangle is 180 degrees is proved convincingly.

• 7:33Speaker 01

  And it comes as a surprise that that can be done.

• 7:38Lex Fridman?

  Why is that surprising? The, well, it is a surprising, surprising idea, I suppose. Why is that proved difficult?

• 7:49Speaker 01

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

• 7:54Lex Fridman?

  Do you remember what is the proof that it adds up to 180?

• 7:59Speaker 01

  You start at a corner and draw a line

• 8:09Speaker 01

  parallel to the opposite side.

• 8:13Speaker 01

  And that line sort of trisects the angle

• 8:19Speaker 01

  between the other two sides.

• 8:22Speaker 01

  And you get a half plane, which has to add up to 180 degrees. And it consists, and the angles by the equality of alternate angles. What's it called? You get a correspondence between the angles created by the side, along the side of the triangle and the three angles of the triangle.

• 8:51Lex Fridman?

  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 to, the puzzles, the visual aspects that were first so compelling to you?

• 9:08Speaker 01

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

• 9:28Lex Fridman?

  Right. You go by the algebra, the linear algebra and not by the visualization?

• 9:35Speaker 01

  Well, the interpretation in terms of, for example, finding the highest point on a polyhedron, as in linear programming, is motivating. But again, I don't have the high dimensional intuition that would particularly inform me. So I sort of lean on the algebra.

• 10:01Lex Fridman?

  So to linger on that point, what kind of visualization do you, do you do when you're trying to think about, we'll get to combinatorial algorithms, but just algorithms in general?

• 10:14Speaker 01

  Yeah.

• 10:15Lex Fridman?

  What kind of, what's inside your mind when you're thinking about designing algorithms? Or even just tackling any, any mathematical problem?

• 10:26Speaker 01

  Well, I think that usually an algorithm is involves a repetition of some inner loop. And and so I can sort of visualize the the distance from the desired solution as iteratively reducing until you finally hit the exact solution.

• 10:50Lex Fridman?

  And try to take steps that get you closer to the

• 10:52Speaker 01

  Try to get to take steps that get closer and having the certainty of converging. So it's it's very it's basically the the mechanics of the algorithm is often very simple. But especially when you're trying something out on the computer. So for example,

• 11:13Speaker 01

  I did some work on the traveling salesman problem and 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.

• 11:28Lex Fridman?

  You mean, so first of all, traveling salesman problem is where you have to visit every city without ever the only ones.

• 11:38Speaker 01

  Yeah, that's right. Find the shortest path through the cities.

• 11:41Lex Fridman?

  Yeah, which is sort of a canonical, a standard, a really nice problem. It's really hard.

• 11:47Speaker 01

  Right, exactly.

• 11:49Lex Fridman?

  So can you say again, what was nice about the objective? Being able to think about the objective function there and maximizing it or minimizing it?

• 11:58Speaker 01

  Well, it's just that the as the algorithm proceeded, it was you were making progress, continual progress and and eventually getting to the optimum point.

• 12:10Lex Fridman?

  So there's two, two parts, maybe, maybe you can correct me. But first is like getting an intuition about what the solution would 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. What part is harder for you? Where's 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 going to run at this at a certain complexity?

• 12:49Speaker 01

  Well, the magic is just the fact that it. That the gap from the optimum decreases monotonically and you can see it happening. And various metrics of what's going on are improving all along until we finally hit the optimum. Perhaps later, we'll talk about the assignment problem and I can illustrate.

• 13:15Lex Fridman?

  Illustrate a little better.

• 13:16Speaker 01

  Yeah.

• 13:17Lex Fridman?

  Now, zooming out again, as you write, Don Knuth has called attention to a breed of people who derive great aesthetic pleasure from contemplating the structure of computational processes. So Don calls these folks geeks. 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.

• 13:41Speaker 01

  Right.

• 13:42Lex Fridman?

  So perhaps you can explain what the assignment problem is and what the Hungarian algorithm is.

• 13:48Speaker 01

  So in the assignment problem, you have N boys and N girls. And you are given the desirability of, 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 costs will be minimized. So the best way to match the boys with the girls, or men with jobs, or any two sets.

• 14:33Lex Fridman?

  Now, any possible matching is possible?

• 14:37Speaker 01

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

• 14:49Lex Fridman?

  Yeah.

• 14:50Speaker 01

  So what you do is to depend on the observation that the identity of the optimal assignment, or as we call it, the optimal permutation, is not changed if you subtract

• 15:17Speaker 01

  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. Because your penal, 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 entire columns

• 15:58Speaker 01

  in such a way that you subtract the same constant from all the elements of that row or column, while maintaining the property that all the elements are non-negative.

• 16:15Lex Fridman?

  Simple.

• 16:16Speaker 01

  Yeah, and so, and so, what you have to do is, is find small moves which will decrease the total cost while 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. And you just keep going in this way until you finally get a full permutation of zeros while the matrix is non-negative. And then you know that that has to be the cheapest.

• 16:55Lex Fridman?

  Is that as simple as it sounds? So the, the shortest path to the matrix part?

• 17:02Speaker 01

  Yeah, the simplicity lies in how you find the, what I oversimplified slightly, what you, you, you will end up subtracting a constant from some rows or columns and adding the same constant back to other rows and columns. So as not to, not to reduce any of the zero elements, you leave them unchanged. But.

• 17:33Speaker 01

  Each individual step modifies us several rows and columns by the same amount, but overall decreases the cost.

• 17:43Lex Fridman?

  So there's something about that elegance that made you go, aha, this is a beautiful, like, it's amazing that something like this, something so simple can solve a problem like this.

• 17:55Speaker 01

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

• 18:22Lex Fridman?

  So what do you think about this idea of geeks, as Don Knuth calls them? What do you think of, is it something 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? Were you born this way?

• 18:45Speaker 01

  I think so. I always like to play with numbers. 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.

• 19:09Lex Fridman?

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

• 19:20Speaker 01

  Right.

• 19:21Lex Fridman?

  A couple of four-digit numbers.

• 19:23Speaker 01

  Yeah, I had a summer job at a beach resort outside of Boston.

• 19:31Speaker 01

  The other employee, I was the Barker at a skee ball game.

• 19:37Lex Fridman?

  Yeah.

• 19:37Speaker 01

  I used to, I used to sit at a microphone, microphone saying, come one, come all, come in and play skee ball, five cents to play, nickel to win, and so on.

• 19:47Lex Fridman?

  That's what a Barker, I was gonna, I wasn't sure if I should know, but Barker, that's, you're the, the charming outgoing person is getting people to come in.

• 19:58Speaker 01

  Yeah, well, I wasn't particularly charming, but I could be very repetitious and loud. And the other employees were sort of juvenile delinquents who had no academic bent. But somehow I found that I could impress them by, by performing this mental melter of mental arithmetic.

• 20:23Lex Fridman?

  Yeah, there's something to that, that, you know, one of, some of the most popular videos on the internet is, there's a YouTube channel called Number File that shows off different mathematical ideas.

• 20:37Speaker 01

  I see.

• 20:37Lex Fridman?

  There's still something really profoundly interesting to people about math. The, the beauty of it, something, even if they don't understand the basic concept of even being discussed, there's something compelling to it. What do you think that is? Any lessons you drew from the, your early teen years where you were showing off to your friends with the numbers? 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 mathematicians?

• 21:13Speaker 01

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

• 21:29Lex Fridman?

  Yeah.

• 21:30Speaker 01

  And that's a kind of achievement. It's, 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.

• 21:49Lex Fridman?

  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 prove it is a powerful step.

• 22:04Speaker 01

  Yeah.

• 22:04Lex Fridman?

  It's amazing that we can do it.

• 22:05Speaker 01

  Of course, another attribute of geeks is they not necessarily end up with emotional intelligence, so they can live in a world of abstractions without having to master the complexities of dealing with people.

• 22:23Lex Fridman?

  So, just to linger on the historical note, as a PhD student in 1955, you joined the computational lab at Harvard where Howard Akin had built the Mark I and the Mark IV computers. Just to take a step back into that history, what were those computers like?

• 22:43Speaker 01

  The Mark IV filled a large room, much bigger than this large office that we're talking in now. And you could walk around inside it. There were rows of relays. You could just walk around the interior and the machine would sometimes fail because of bugs, which literally meant flying creatures landing on the switches.

• 23:16Speaker 01

  So, I never used that machine for any practical purpose.

• 23:23Speaker 01

  The lab eventually acquired one of the earlier commercial computers.

• 23:31Lex Fridman?

  This is already in the 60s?

• 23:33Speaker 01

  No, in the mid 50s.

• 23:34Lex Fridman?

  The mid 50s?

• 23:35Speaker 01

  Late 50s.

• 23:36Lex Fridman?

  There was already commercial computers in the...

• 23:38Speaker 01

  Yeah, we had a Univac, a 2000, Univac with 2,000 words of storage. And so, you had to work hard to allocate the memory properly to... Also, the access time from one word to another depended on the...

• 23:55Speaker 01

  Number of the particular words and so you there was an art to sort of arranging the storage allocation to make fetching data rapid.

• 24:07Lex Fridman?

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

• 24:20Speaker 01

  No, not at all. I think I was I was attracted to the underlying algorithms.

• 24:27Lex Fridman?

  So but did you draw any inspiration? 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 would have billions of these computers all over the world?

• 24:42Speaker 01

  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 going to be really big and I should get into it.

• 25:03Lex Fridman?

  She's a smart woman.

• 25:04Speaker 01

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

• 25:23Lex Fridman?

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

• 25:39Speaker 01

  Yeah.

• 25:39Lex Fridman?

  As something that could one day have human level intelligence?

• 25:43Speaker 01

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

• 25:52Lex Fridman?

  The Turing test, computing and intelligence?

• 25:55Speaker 01

  Yeah, the Turing test.

• 25:57Lex Fridman?

  What did you think about that paper? Was that just like science fiction?

• 26:01Speaker 01

  I thought that it wasn't a very good test because it was too subjective. So I didn't feel that, I didn't feel that the Turing test was really the right way to calibrate how intelligent an algorithm could be.

• 26:17Lex Fridman?

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

• 26:26Speaker 01

  Yeah.

• 26:26Lex Fridman?

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

• 26:38Speaker 01

  Yeah.

• 26:38Lex Fridman?

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

• 26:48Speaker 01

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

• 26:55Lex Fridman?

  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?

• 27:12Speaker 01

  It's an open question.

• 27:15Speaker 01

  It seems to me that most of the achievements have acquire, 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

• 27:51Speaker 01

  physical attributes for acquire, for exploring their environment. They have intuition, they have desires,

• 28:02Speaker 01

  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.

• 28:17Speaker 01

  Computer program which surpasses a six-month-old child in terms of comprehension of the world.

• 28:27Lex Fridman?

  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 a set of algorithms or an algorithm? So can a Turing machine achieve human-level intelligence?

• 28:50Speaker 01

  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 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 simulation outside. But while that may be true in principle,

• 29:34Speaker 01

  that cannot be the way we're eventually going to tackle this problem. It's, you know, that does not seem like a feasible way to go about it. So there is, however, an existence proof that if you believe that the brain is just a network of neurons operating by rules, I guess you could say that that's an existence proof of the ability to build the capabilities of a mechanism. But it would be almost impossible to acquire the information.

• 30:15Speaker 01

  Unless we got enough insight into the operation of the brain.

• 30:19Lex Fridman?

  But there's so much mystery there. Do you think, what do you make of consciousness? For example, there's something, as an example of something we completely have no clue about. The fact that we have this subjective experience.

• 30:32Speaker 01

  Right.

• 30:32Lex Fridman?

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

• 30:41Speaker 01

  To know its own identity.

• 30:43Lex Fridman?

  Yeah, to know, to know the algorithm to know itself.

• 30:47Speaker 01

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

• 30:53Lex Fridman?

  Yeah.

• 30:56Speaker 01

  So I know that there are many who believe that general intelligence can be achieved. And there are even some who are, feel certain that the singularity will come and 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.

• 31:29Lex Fridman?

  Just for the fun of it, could you linger on why, what's your intuition, why you're doubtful? So there are quite a few people that are extremely worried about this existential threat of artificial intelligence, of us being left behind by the super intelligent new species. What's your intuition, why that's not quite likely?

• 31:54Speaker 01

  Just because none of the achievements in speech or robotics or natural language processing or creation of.

• 32:07Speaker 01

  Flexible computer assistants or any of that comes anywhere near close to that level of cognition.

• 32:17Lex Fridman?

  What do you think about ideas of sort of, if we look at Moore's law and exponential improvement to allow us to, that would surprise us? Sort of our intuition fall apart with exponential improvement because, I mean, we're not able to kind of, we kind of think in linear improvement.

• 32:34Speaker 01

  Yeah.

• 32:35Lex Fridman?

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

• 32:43Speaker 01

  Yeah.

• 32:44Lex Fridman?

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

• 33:04Speaker 01

  I don't think any constant factor improvement could, could change things. And given, given our current comprehension of how the, of, of what cognition requires, it seems to me that multiplying the speed of the switches by a factor of a thousand or a million will not be useful until we really understand the organizational principle behind the network of switches.

• 33:40Lex Fridman?

  Well, let's jump into the network of switches and talk about combinatorial algorithms, if we could.

• 33:46Lex Fridman?

  Let's step back for the very basics. What are combinatorial algorithms? And what are some major examples of problems they aim to solve?

• 33:55Speaker 01

  A combinatorial algorithm is, is one which deals with a, a system of discrete objects that can occupy various states or take on various values from a discrete set of values and need to be arranged or, or selected in such a way as to achieve some.

• 34:27Speaker 01

  To minimize some cost function, or to prove the existence of some combinatorial configuration. So, an example would be coloring the vertices of a graph.

• 34:41Lex Fridman?

  What's a graph? Let's step back. So, it's fun 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 a graph?

• 35:01Speaker 01

  A graph? That's simple. 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 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.

• 35:36Lex Fridman?

  And they could be directed or undirected. And then, as you've mentioned before, might have costs.

• 35:42Speaker 01

  Right, they can be directed or undirected. You can think of them as, 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 optimizing the efficiency of such networks, or learning about the performance of such networks.

• 36:24Speaker 01

  Are the object of combinatorial algorithms. So it could be scheduling classes at a school where the the vertices, the nodes of the network are the individual classes and the edges indicate the constraints which say that certain classes cannot take place at the same time or certain teachers are available only for certain classes, et cetera. Or I talked earlier about the assignment problem of matching the boys with the girls.

• 37:04Speaker 01

  Where you have the graph with an edge from each boy to each girl with a weight indicating the cost. Or in logical design of computers, you might want to find a set of so-called gates, switches that perform logical functions which can be interconnected to realize some function. So you you might ask,

• 37:37Speaker 01

  how many gates do you need in order to

• 37:43Speaker 01

  for a for a circuit to give a yes output if at least a given number of its inputs are ones and no if not if fewer are present?

• 37:59Lex Fridman?

  My favorite is probably all the all the work with network flows. So anytime you have, 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 in communication networks.

• 38:14Lex Fridman?

  And traffic.

• 38:16Speaker 01

  Right.

• 38:17Lex Fridman?

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

• 38:32Speaker 01

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

• 38:46Lex Fridman?

  Maybe supply chain as well, like products being.

• 38:50Speaker 01

  Products flowing from one operation to another.

• 38:53Lex Fridman?

  Yeah.

• 38:54Speaker 01

  And the edges have a capacity, which is the rate at which the commodity can flow. And a central problem is to determine, given a network of these channels, in this case, the edges are communication channels.

• 39:13Speaker 01

  The challenge is to find the maximum rate at which the information can flow along these channels to get from a source to a destination. And that's a fundamental combinatorial problem that I've worked on. Jointly with the scientist Jack Edmonds, we, I think, were the first to give a formal proof that this maximum flow problem through a network can be solved in polynomial time.

• 39:47Lex Fridman?

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

• 40:07Speaker 01

  Yes, probably.

• 40:08Lex Fridman?

  Okay, so yeah, I remember being very surprised that MaxFlow is a polynomial time algorithm.

• 40:13Speaker 01

  Yeah.

• 40:13Lex Fridman?

  That there's a nice, fast algorithm that solves MaxFlow. But, so there is an algorithm named after you, in Edmonds. The Edmonds-Karp algorithm for MaxFlow. 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?

• 40:37Speaker 01

  Yeah. Well, first of all, what is a polynomial time algorithm?

• 40:42Lex Fridman?

  Yeah.

• 40:42Speaker 01

  Perhaps we could. Discuss that.

• 40:45Lex Fridman?

  So yeah, let's, let's actually just even, yeah, that's what is algorithm, algorithmic complexity? What are the major classes of algorithm complexity?

• 40:55Speaker 01

  So we, in a, in a problem like the assignment problem, or scheduling schools, or any of these applications, you have a set of input data, which might, for example, be a set of vertices connected by edges with, you're given for each edge, the capacity of the edge. And you have algorithms which are, I think of them as computer programs with operations such as addition, subtraction, multiplication, division, comparison of

• 41:37Speaker 01

  numbers, and so on. And you're trying to construct an algorithm 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, the configuration of the network that carries the maximum amount of flow. And an algorithm is said to run in polynomial time if, as

• 42:19Speaker 01

  a function of the size of the input, the number of vertices, the number of edges, and so on, the number of basic computational steps grows only as some fixed power of that size. A linear algorithm would

• 42:37Speaker 01

  Execute a number of steps linearly 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.

• 42:56Lex Fridman?

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

• 43:01Speaker 01

  That's right. Theoreticians take that to be the definition of an algorithm being efficient. 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.

• 43:32Lex Fridman?

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

• 43:48Speaker 01

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

• 44:06Lex Fridman?

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

• 44:19Speaker 01

  Yeah.

• 44:20Lex Fridman?

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

• 44:22Speaker 01

  Yeah.

• 44:23Lex Fridman?

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

• 44:30Speaker 01

  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 then there's that the class of such algorithms is called P.

• 44:46Lex Fridman?

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

• 44:48Speaker 01

  Yeah.

• 44:48Lex Fridman?

  So for every case of the problem.

• 44:50Speaker 01

  And that's very important that in this theory, um, when we measure the complexity of an algorithm, we really measure the number of step, 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

• 45:32Speaker 01

  from the point of view of their worst case performance and yet are very effective. So, so theoreticians are interested in P, the class of problem 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,

• 46:12Speaker 01

  you have the number of numbers that you need to write down to specify the problem instances, N squared. And the question is, um,

• 46:25Speaker 01

  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.

• 46:37Speaker 01

  Earlier algorithms required into 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 verify that a solution is optimal? So for example, if if the input was a graph, we might want to find the largest clique in the graph. Or a clique is a set of vertices such that any vertex, each vertex in the set is adjacent to each of the others.

• 47:20Speaker 01

  So the clique is a complete subgraph.

• 47:25Lex Fridman?

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

• 47:32Speaker 01

  That would be what's called a complete graph. It would be.

• 47:35Lex Fridman?

  No, I mean, within that clique.

• 47:37Speaker 01

  Within that clique, yeah.

• 47:41Speaker 01

  They're all friends.

• 47:42Lex Fridman?

  So a complete graph is when.

• 47:44Speaker 01

  Everybody is friendly.

• 47:45Lex Fridman?

  As everybody is friends with everybody.

• 47:47Speaker 01

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

• 48:24Lex Fridman?

  And that's a polynomial time.

• 48:27Speaker 01

  That's a polynomial. So the verify there, the problem of finding the clique.

• 48:34Speaker 01

  Appears to be extremely hard, but the problem of verifying a clique, to see if it reaches a target number of vertices, is easy to solve, is easy to verify. So finding the clique is hard, checking it is easy. Problems of that nature are called non-deterministic polynomial time algorithms. And that's the class NP.

• 49:02Lex Fridman?

  And what about NP complete and NP hard?

• 49:05Speaker 01

  Okay. Let's talk about problems where you're getting a yes, no, a yes or no answer, rather than a numerical value. So either there is a, a perfect matching of the, of the, uh, boys with the girls, or there isn't. It's clear that, um, every problem in P is also in NP. If you can solve the problem exactly, then you can certainly verify the solution. On the other hand, there are problems in the class NP. This is the class of problems that are easy to check, although they may be hard to solve. It's not at all clear that problems in NP lie in P.

• 49:50Speaker 01

  So for example, if we're looking at scheduling classes at a school, the fact that you can verify when handed a schedule for the school, whether it meets all the requirements, that doesn't mean that you can find the schedule rapidly. So intuitively, NP, non-deterministic polynomial, checking rather than finding, is going to be harder than, is going to include, is easier. Checking is easier, and therefore the class of problems that can be checked appears to be much larger than the class of problems that can be solved.

• 50:31Lex Fridman?

  And then you keep adding appears to, and, uh, sort of these, uh, additional words that designate that we don't know for sure yet.

• 50:41Speaker 01

  We don't know for sure. 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. Question is whether P is equal to NP. If P were equal to NP, it would be amazing. It would mean that every

• 51:09Speaker 01

  problem where a solution can be rapidly checked

• 51:15Speaker 01

  can actually be solved in polynomial time. We don't really believe that's true. If you're scheduling classes at a school,

• 51:24Speaker 01

  it's, we 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.

• 51:41Lex Fridman?

  So can 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?

• 52:05Speaker 01

  I would bet that P is unequal to NP, 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 no polynomial time algorithms have been found for these easy to check problems. So one example is a problem that goes back to the mathematician Gauss, who was interested in factoring large numbers. So we know what a number is prime if it doesn't, if it cannot be written

• 52:46Speaker 01

  as the product of two or more numbers unequal to 1.

• 52:53Speaker 01

  So if we can factor the number like 91 at 7 times 13.

• 53:00Speaker 01

  But if I give you

• 53:05Speaker 01

  Twenty-digit or thirty-digit numbers, you're probably going to be at a loss to have any idea whether they can be factored. So the problem of factoring very large numbers is does not appear to have an efficient solution. But once you have found the factors, expressed the number as a product, the two smaller numbers, you can quickly verify that they are factors of the number.

• 53:36Lex Fridman?

  And your intuition is a lot of people finding, you know, there's 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 it would be great to find an efficient algorithm for.

• 53:50Speaker 01

  Right, and in fact, we have some results that I was instrumental in obtaining, following up on work by the mathematician Stephen Cook, to show that 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, we would also know that

• 54:32Speaker 01

  virtually all the standard combinatorial problems, if P is unequal to NP, none of them can be solved in polynomial time.

• 54:42Lex Fridman?

  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?

• 54:53Speaker 01

  The first and most important stage of progress was a result by Stephen Cook, who showed that a certain problem called the satisfiability problem of propositional logic is as hard as any problem in the class P. So the propositional logic problem is expressed in terms of expressions involving the logical operations and/or and not operating operating on variables that can be either true or false.

• 55:36Speaker 01

  So an instance of the problem would be some formula involving and/or and not. 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 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 assignment of truth values to the variables A and B

• 56:18Speaker 01

  will allow that conjunction of what are called clauses to be true. So that's an example of a formula in propositional logic involving expressions based on the operations and/or and not. That's an example of a problem which is not satisfiable. There is no solution that satisfies all of those constraints.

• 56:48Lex Fridman?

  And that's like one of the cleanest and fundamental problems in computer science. It's like a nice statement of a really hard problem.

• 56:54Speaker 01

  It's a nice statement of a really hard problem. And what Cook showed is that every problem in NP is can be re-expressed as an instance of the satisfiability problem. So to do that, he used the observation that a very simple abstract machine called the Turing machine. Can be used to describe any algorithm.

• 57:31Speaker 01

  An algorithm for any realistic computer can be translated into an equivalent algorithm on one of these Turing machines, which are extremely simple.

• 57:44Lex Fridman?

  So Turing machine, there's a tape and you can

• 57:47Speaker 01

  Yeah, you have

• 57:48Lex Fridman?

  Walk along that

• 57:49Speaker 01

  Data on a tape and you have basic instructions, a finite list of instructions which say, which say if you're reading a particular symbol on the tape and you're in a particular state, then you can move to 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.

• 58:12Lex Fridman?

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

• 58:19Speaker 01

  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.

• 58:38Lex Fridman?

  Right.

• 58:39Speaker 01

  And then using that fact, he could sort of describe any possible non-deterministic polynomial time algorithm, any algorithm for a problem in NP could be expressed as a sequence of moves of the Turing machine, described in terms of reading a symbol on the tape while you're in a given state and moving to a new state and leaving behind a new symbol. And given that, the fact that any non-deterministic polynomial time algorithm

• 59:24Speaker 01

  can be Described by a list of such instructions, you could translate the problem into the language of the satisfiability problem.

• 59:36Lex Fridman?

  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?

• 59:43Speaker 01

  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 tells us that this, of all the problems in NP, all the problems where solutions are easy to check, they can, they can all be rewritten in terms of the satisfiability problem.

• 1:00:16Lex Fridman?

  Yes, in adding so much more weight to the P equals NP question. Because all it takes is to show that one.

• 1:00:26Speaker 01

  That's right.

• 1:00:26Lex Fridman?

  One algorithm in this class.

• 1:00:28Speaker 01

  So the P versus NP can be re-expressed as simply asking whether the satisfiability problem of propositional logic is solvable in polynomial time.

• 1:00:40Speaker 01

  But there's more.

• 1:00:44Speaker 01

  I encountered Cook's paper when he published it in a conference in 1971. Yeah, so when I saw Cook's paper and saw this reduction of all, of each of the problems in NP by a uniform method to, to the satisfiability problem of propositional logic,

• 1:01:09Speaker 01

  that meant that the satisfiability problem was a universal combinatorial problem.

• 1:01:16Speaker 01

  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.

• 1:01:32Speaker 01

  And so I began looking for reductions from the satisfiability to other problems.

• 1:01:47Speaker 01

  One of the other problems would be the so-called integer programming problem of solving a determining whether there's a solution to a a set of linear inequalities involving integer variables.

• 1:02:05Lex Fridman?

  Just like linear programming, but there's a constraint that the variables must remain integers.

• 1:02:10Speaker 01

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

• 1:02:15Lex Fridman?

  And that makes the problem much harder.

• 1:02:17Speaker 01

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

• 1:02:30Lex Fridman?

  So can you pause on that? Was that one of the first problem mappings that you tried to do? And how hard is that mapping? You say it wasn't hard to show, but you know, that's a that's a big leap.

• 1:02:44Speaker 01

  It is a big leap, yeah. Well, let me let me give you another example. Another problem in NP is whether a graph contains a clique of a given size.

• 1:02:59Speaker 01

  And now the question is, can we reduce the propositional logic problem to the problem of whether there's a clique of a certain size?

• 1:03:15Speaker 01

  Well, if you look at the propositional logic problem, it can be expressed as a number of clauses, each of which is a

• 1:03:28Speaker 01

  Of the form A or B or C, where A is either one of the variables in the problem or the negation of one of the variables. And the, an instance of the propositional logic problem can be rewritten using operations of Boolean logic, can be rewritten as the conjunction of a set of clauses, the AND of a set of ORs, where each clause is a disjunction, an OR of variables or negated variables.

• 1:04:10Speaker 01

  So the question of, in the satisfiability problem, is whether those clauses can be simultaneously satisfied. Now, to satisfy all those clauses, you have to find one of the terms in each clause, which is going to be given the, which is going to be true in your truth assignment. But you can't make the same variable both true and false. So if you have the variable A in one clause and you want to satisfy that clause by making A true,

• 1:04:51Speaker 01

  you can't also make the complement of A true in some other clause.

• 1:04:56Lex Fridman?

  And so the goal is to make every single clause true, if it's possible, to satisfy this. And the way you make it true is at least...

• 1:05:05Speaker 01

  One term in the clause must be, must be true.

• 1:05:09Lex Fridman?

  Got it.

• 1:05:10Speaker 01

  So now we, to convert this problem to something called the independent set problem, where you're just sort of asking for a set of vertices in a graph, such that no two of them are adjacent, sort of the opposite of the clique problem. So we've seen that we can now express that as...

• 1:05:41Speaker 01

  Finding a

• 1:05:46Speaker 01

  set of terms, one in each clause, without picking both the variable and the negation of that variable. Because if the variable is assigned the truth value, the negated variable has to have the opposite truth value.

• 1:06:03Lex Fridman?

  Right.

• 1:06:04Speaker 01

  And so we can construct a graph where the vertices are the

• 1:06:11Speaker 01

  terms in all of the clauses. And you have an edge between two

• 1:06:24Speaker 01

  terms if

• 1:06:28Speaker 01

  if

• 1:06:30Speaker 01

  an edge between two occurrences of terms, either if they're both in the same clause, because you're only picking one element from each clause. And also an edge between them if they represent opposite values of the same variable, because you can't make a variable both true and false. And so you get a graph where you have all of these occurrences of variables. You have edges, which mean that you're not allowed to choose both ends of the edge, either because they're in the same clause or they're negations of one another.

• 1:07:07Lex Fridman?

  Right, and that's a for sure, sort of to zoom out, that's a really powerful idea that you could take a graph and connect it to a logic equation

• 1:07:19Speaker 01

  Right.

• 1:07:20Lex Fridman?

  somehow. And do that mapping for all possible formulations of a particular problem on a graph.

• 1:07:27Speaker 01

  Yeah.

• 1:07:27Lex Fridman?

  I mean, that

• 1:07:30Lex Fridman?

  that still is hard for me to believe

• 1:07:33Speaker 01

  Yeah.

• 1:07:33Lex Fridman?

  that that's possible. That that there, like, what do you make of that? That there's such a union of there's such a friendship among all these problems across that somehow are akin to combinatorial algorithms, that they're all somehow related.

• 1:07:52Speaker 01

  Yeah.

• 1:07:52Lex Fridman?

  I know it can be proven.

• 1:07:55Speaker 01

  Yeah.

• 1:07:55Lex Fridman?

  But what do you make of it? That that's true?

• 1:07:59Speaker 01

  Well, that they just have the same expressive power. You can take any one of them and translate it into the terms of the other.

• 1:08:09Lex Fridman?

  The fact that they have the same expressive power also somehow means that they can be translatable.

• 1:08:15Speaker 01

  Right. And what I did in the 1971 paper was to take 21 fundamental problems, the commonly occurring problems of packing, covering, matching, and so forth, lying in the class NP, and show that the satisfiability problem can be re-expressed as any of those, that any of those have the same expressive power.

• 1:08:46Lex Fridman?

  And that was like throwing down the gauntlet of saying, there's probably many more problems like this.

• 1:08:52Speaker 01

  Right.

• 1:08:53Lex Fridman?

  But that's just saying that, look, that they're all the same.

• 1:08:56Speaker 01

  They're all the same, but not exactly. They're all the same in terms of whether they are

• 1:09:05Speaker 01

  rich enough to express any of the others.

• 1:09:10Speaker 01

  But that doesn't mean that they have the same computational complexity. But what we can say is that either all of these problems or none of them are solvable in polynomial time.

• 1:09:22Lex Fridman?

  Yeah, so what is NP completeness and NP-hard? As classes say.

• 1:09:28Speaker 01

  Oh, that's just a small technicality. So when we're talking about decision problems, that means that the answer is just yes or no. There is a clique of size 15 or there's not a clique of size 15. On the other hand, an optimization problem would be asking,

• 1:09:48Speaker 01

  find the largest clique. The answer would not be yes or no, it would be 15. So when you're asking for the

• 1:09:59Speaker 01

  When you're putting a valuation on the different solutions, and you're asking for the one with the highest valuation, that's an optimization problem. And there's a very close affinity between the two kinds of problems. But the counterpart of being the hardest decision problem, the hardest yes/no problem, the counterpart of that is to minimize or maximize an objective function. And so a problem that's hardest in the class, when viewed in terms of optimization, those are called NP-hard rather than NP-complete.

• 1:10:41Lex Fridman?

  And NP-complete is for decision problems?

• 1:10:43Speaker 01

  And NP-complete is for decision problems.

• 1:10:46Lex Fridman?

  So if somebody shows that P equals NP, what do you think that proof will look like? If you were to put on yourself, if it's possible to show that as a proof or to demonstrate in an algorithm?

• 1:11:06Speaker 01

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

• 1:11:13Lex Fridman?

  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?

• 1:11:26Speaker 01

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

• 1:11:39Lex Fridman?

  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 linger on it? What kind of impact would it have on theoretical computer science and perhaps software, the systems in general?

• 1:11:59Speaker 01

  Well, I think it would have enormous impact on the world in either way case. If P is unequal to NP, which is what we expect. Then we know that we're in, that for the great majority of the combinatorial problems that come up, since they're known to be NP complete, 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 is not NP, then it can't be solved efficiently on all instances.

• 1:12:42Speaker 01

  But, but basically, it will, it will, if we find that P is unequal to NP, it will mean that we can't 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.

• 1:13:04Lex Fridman?

  So we would turn our eye towards the heuristics with a little bit more acceptance and comfort on our hearts?

• 1:13:13Speaker 01

  Exactly.

• 1:13:14Lex Fridman?

  Okay, so let me ask a romanticized question. 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?

• 1:13:31Speaker 01

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

• 1:13:39Lex Fridman?

  What's the stable matching problem?

• 1:13:41Speaker 01

  Yeah. Imagine that you want to marry off N boys with 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.

• 1:14:09Speaker 01

  Each girl also has a, an ordering of the boys, first choice, second choice, and so on. And we'll say, and we, we'll say that a matching, a 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, the matching is stable if there is no pair who want to run away with each other, leaving their partners behind.

• 1:14:55Lex Fridman?

  Gotcha.

• 1:15:00Lex Fridman?

  Yeah.

• 1:15:01Speaker 01

  Actually, this is relevant to matching residents with hospitals and some other real-life problems, although not quite in the form that I described. So it turns out that there is, that a stable, for any set of preferences, a stable matching exists. And moreover, it can be computed by a simple algorithm in which each boy starts making proposals to girls. And if the girl receives a proposal, she accepts it tentatively, but

• 1:15:43Speaker 01

  she can drop it, if, she can end, 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, you know, stopping when...

• 1:16:03Speaker 01

  A proposal is accepted. But the girls meanwhile are watching the proposals that are coming into them. And the girl will drop her current partner. If she gets a better proposal.

• 1:16:20Lex Fridman?

  And the boys never go back through.

• 1:16:22Speaker 01

  They never go back. Yeah. So once they've been denied.

• 1:16:28Lex Fridman?

  They don't try again.

• 1:16:29Speaker 01

  They don't, they don't, they don't try again because the girls are always improving their status as they get more, as they receive better and better proposals. The boys are going down their list, starting with their top preferences. And

• 1:16:48Speaker 01

  one can prove that

• 1:16:52Speaker 01

  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 abscond from each other.

• 1:17:07Lex Fridman?

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

• 1:17:21Speaker 01

  Both, I would say. And you also have the observation that you might ask, 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's the boys who are doing, doing the best. And as each boy is doing at least as well as he could do in any other staple matching. So there's a sort of lesson for the boys that you should go out and be proactive and make those proposals. Go for broke.

• 1:17:57Lex Fridman?

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

• 1:18:11Speaker 01

  Yeah, well, you get, you, you get complications. For example, what happens when a husband and wife want to be assigned to the same hospital? So you, you, you have to take those constraints into account. And then the problem becomes NP hard.

• 1:18:32Lex Fridman?

  Why is it a problem for the husband and wife to be assigned to the same hospital?

• 1:18:36Speaker 01

  No, it's desirable.

• 1:18:38Lex Fridman?

  Desirable.

• 1:18:39Speaker 01

  Or at least go to the same city. So you can't, if you're, if you're assigning residents to hospitals.

• 1:18:46Lex Fridman?

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

• 1:18:51Speaker 01

  The residents have their own preferences.

• 1:18:55Speaker 01

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

• 1:19:21Lex Fridman?

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

• 1:19:24Speaker 01

  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 to, have to be assigned to the same place.

• 1:19:39Lex Fridman?

  I'm being a little dense.

• 1:19:43Lex Fridman?

  The, what, sort of, the perfect matching? No, not the perfect, stable matching is what you referred to. That's when two partners are trying to.

• 1:19:53Speaker 01

  Okay, what's confusing you is that in the first interpretation of the problem, I had boys matching with girls.

• 1:19:59Lex Fridman?

  Yes.

• 1:20:01Speaker 01

  In the second interpretation, you have humans matching with institutions.

• 1:20:06Lex Fridman?

  Institutions. And there's a coupling between within the, gotcha, within the humans. Any added little constraint will make it an NP-hard problem.

• 1:20:17Speaker 01

  Well, yeah.

• 1:20:20Lex Fridman?

  Okay.

• 1:20:22Lex Fridman?

  By the way, the argument you mentioned wasn't, was it one of yours or?

• 1:20:24Speaker 01

  No, no, that was due to Gail and Shapley. And my friend David Gill passed away before he could get part of the Nobel Prize. But his partner Shapley shared in a Nobel Prize with somebody else for.

• 1:20:41Lex Fridman?

  Economics?

• 1:20:42Speaker 01

  For, for, for economics. For ideas stemming from the stable matching idea.

• 1:20:49Lex Fridman?

  So you've also have developed yourself some elegant, beautiful algorithms. Again, picking your children, so the Robin Karp algorithm for string searching, pattern matching, Edmonds 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 whether it's beauty, elegance, or just being the right discovery development in your life that you're especially proud of?

• 1:21:25Speaker 01

  I like the Robin Karp algorithm because it illustrates the power of randomization. So the problem there is to decide whether a given long string of symbols from some alphabet contains a given word, whether a particular word occurs within some very much longer word.

• 1:22:02Speaker 01

  And so the idea of the algorithm is to associate with the word that we're looking for, a fingerprint, 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 associate with each word a number.

• 1:22:43Speaker 01

  So we, first of all, we think of the letters that occur in a word as the digits of, let's say, decimal or whatever base here.

• 1:22:55Speaker 01

  Whatever number of different symbols there are.

• 1:22:58Lex Fridman?

  That's the base of the of the numbers. Yeah.

• 1:23:01Speaker 01

  Right. So every word can then be thought of as a number with the letters being the digits of that number. 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.

• 1:23:29Lex Fridman?

  So coming up with a nice hash function.

• 1:23:31Speaker 01

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

• 1:23:33Lex Fridman?

  Yeah.

• 1:23:35Lex Fridman?

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

• 1:23:39Speaker 01

  Yeah, that. So that's the that's the.

• 1:23:43Lex Fridman?

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

• 1:23:52Speaker 01

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

• 1:23:59Lex Fridman?

  Yes.

• 1:24:00Speaker 01

  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 a certain size, the size of the word we're looking for. And we we compute the fingerprint of every say, stretch of that length. And it turns out that just a couple of arithmetic 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

• 1:24:42Speaker 01

  simple. And secondly,

• 1:24:46Speaker 01

  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.

• 1:24:58Lex Fridman?

  Right.

• 1:24:58Speaker 01

  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.

• 1:25:12Lex Fridman?

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

• 1:25:35Speaker 01

  Well, it's just the ability to draw a random number from such, from some range, or to associate a random number with some object, or to draw at random from some set. So another example is very simple. If we're conducting a presidential election, and we would like to pick the winner, in principle, we could draw a random sample of all of the voters in the country.

• 1:26:17Speaker 01

  And if it was 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. And 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 we wouldn't have a significant difference between two candidates.

• 1:26:53Lex Fridman?

  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 a...

• 1:27:00Speaker 01

  You just that random picking would be, would solve the problem with a very, with a very low probability of error. Another example is testing whether a number is prime. So if I want to test whether... Seventeen is prime. I could pick any number between one and seventeen, and raise it to the sixteenth power modulo seventeen, and you should get back the original number. That's a famous formula due to Fermat about, it's called Fermat's Little Theorem,

• 1:27:38Speaker 01

  that if you take any a, any number a in the range, zero through n minus one, and raise it to the n minus one power modulo n, you'll get back the number a. If the number is, if a is prime.

• 1:28:00Lex Fridman?

  Yeah.

• 1:28:00Speaker 01

  So if you don't get back the number a, that's a proof that a number is not prime.

• 1:28:06Lex Fridman?

  Oh.

• 1:28:09Speaker 01

  And you can show that suitably define the probability that you will get a value unequal, you will get a violation of Fermat's result, is very high. And so this gives you a way of rapidly proving that a number is not prime. It's a little more complicated than that because there are certain values of n where something a little more elaborate has to be done, but that's the basic idea. Taking an identity that holds for primes,

• 1:28:51Speaker 01

  and therefore, if it ever fails on any instance for a non-prime, you know the number is not prime. It's a quick choice, a fast choice, fast proof that a number is not prime.

• 1:29:05Lex Fridman?

  Can you maybe elaborate a little bit more? What's your intuition why randomness works so well and results in such simple algorithms?

• 1:29:14Speaker 01

  Well, the example of conducting an election where you could take, in theory, you could take a sample and depend on the validity of the sample to really represent the whole. It's just the basic fact of statistics, which gives a lot of opportunities.

• 1:29:34Speaker 01

  And I actually exploited that sort of random sampling idea in designing an algorithm for counting the number of solutions that satisfy a particular formula in propositional logic.

• 1:29:54Lex Fridman?

  A particular, so some version of the satisfiability problem?

• 1:30:00Speaker 01

  A version of the satisfiability problem.

• 1:30:04Lex Fridman?

  Is there some interesting insight that you want to elaborate on? Like what, some aspect of that algorithm that might be useful to describe?

• 1:30:14Speaker 01

  So you have a collection of formulas and you want to count the number of solutions that satisfy at least one of the formulas.

• 1:30:37Speaker 01

  And you can count the number of solutions that satisfy any particular one of the formulas, but you have to account for the fact that that solution might be counted many times if it solves more than one of the formulas.

• 1:30:57Speaker 01

  And so what you do is you sample from the formulas according to the number of solutions that satisfy each individual one. In that way, you draw a random solution, but then you correct by looking at the number of formulas that satisfy that random solution.

• 1:31:21Speaker 01

  And don't double count. So if you, you can think of it this way. So you have a matrix of zeros and ones, and you want to know how many columns of that matrix contain at least one one.

• 1:31:39Speaker 01

  And you can count in each row how many ones there are. So what you can do is draw from the rows according to the number of ones. If a row has more ones, it gets drawn more frequently. But then, if you draw from that row, you have to go up the column and looking at where that same one is repeated in different rows. And only count it as a success or a hit if it's the earliest row that contains the one.

• 1:32:11Lex Fridman?

  Right.

• 1:32:12Speaker 01

  And that gives you a robust statistical estimate of the total number of columns that contain at least one of the ones. So that is an example of the same principle that was used in studying random sampling. Another viewpoint is that if you have a phenomenon that occurs almost all the time, then if you sample one of the occasions where it occurs, you're most likely to, and you're looking for an occurrence, a random occurrence is likely to work.

• 1:32:51Speaker 01

  So that comes up in solving identities, solving algebraic identities. You get two formulas that may look very different. You want to know if they're really identical. What you can, what you can do is just pick a random value and evaluate the formulas at those two, at that value and see if they, seeing if they agree. And you depend on the fact that if the formulas are distinct, then they're going to disagree a lot. And so therefore, a random choice will exhibit the disagreement. And if there are many ways for the two to disagree,

• 1:33:33Speaker 01

  and you only need to find one disagreement, then random choice is likely to yield it.

• 1:33:39Lex Fridman?

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

• 1:33:54Speaker 01

  Right.

• 1:33:54Lex Fridman?

  Could you maybe comment on?

• 1:33:58Lex Fridman?

  The usefulness and the power of worst-case analysis versus best-case analysis, average-case probabilistic. 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?

• 1:34:23Speaker 01

  Yeah.

• 1:34:24Lex Fridman?

  And what are the challenges there?

• 1:34:26Speaker 01

  So if worst-case analysis shows that an algorithm is always good, that's fine. If worst-case analysis 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 ask, how often will you get a good solution?

• 1:34:52Lex Fridman?

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

• 1:35:05Speaker 01

  Right, and that's unfortunate. I think a good example is going back to the satisfiability problem. 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. And so in many application areas, even though satisfiability, as we've already discussed,

• 1:35:44Speaker 01

  is NP-complete, the SAT solvers will work so well that the people in that discipline tend to think of satisfiability as an easy problem. So, in other words, 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 satisfiability is not hard to check.

• 1:36:21Speaker 01

  And even searching for a satisfying solution can be done efficiently in practice. And there are many examples. For example, we talked about the traveling salesman problem. So just to refresh our memories, the problem is you've got a set of cities. You have pairwise distances between cities. And you want to find a tour through all the cities that minimizes the total the total cost of all the edges traversed, all the trips between cities. The problem is NP-hard, but people using integer programming codes,

• 1:37:03Speaker 01

  together with some other mathematical tricks, can solve geometric instances of the problem where the cities are, let's say, points in the plane, 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 2, it'll rapidly get optimal solutions, provably optimal solutions, even though, again, we know that it's unlikely that the traveling salesman problem can be solved in polynomial time.

• 1:37:45Lex Fridman?

  Are there methodologies, like rigorous systematic methodologies for... You said "in practice." In practice, this algorithm sounds pretty good. Are there systematic ways of saying, "In practice, this one's 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 cases, typical instances, and that might be really difficult.

• 1:38:12Speaker 01

  That's very difficult. So after I did my original work on getting...

• 1:38:20Speaker 01

  Showing all these problems to be 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 problems, behavior on the average or with high probability. But I had to make some assumptions about 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

• 1:39:02Speaker 01

  of vertices and edges, then we would generate the graph by simply choosing one edge at a time 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 could prove all kinds of wonderful things, I and others who also worked on this. So we could show that we know exactly how many edges there have to be in order for there be a so-called Hamiltonian circuit.

• 1:39:41Speaker 01

  That's a a cycle that visits each vertex exactly once. We know that if the 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 the community in which I was working got a lot of results along these lines. But the field tended to be rather lukewarm about accepting these results as meaningful

• 1:40:24Speaker 01

  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

• 1:40:39Speaker 01

  Concluded that

• 1:40:43Speaker 01

  that it didn't have a lot of bite in terms of the practical application.

• 1:40:48Lex Fridman?

  Oh, the, okay, so there's too much into the world of toy problems.

• 1:40:52Speaker 01

  Yeah.

• 1:40:52Lex Fridman?

  That can, okay, but, all right, but is there a way to find nice representative, real world impactful instances of a problem on which 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 data set from like the real world and show the performance, all the, all the conferences are all focused on beating the performance of, on that real world data set. Is there an equivalent in complexity analysis?

• 1:41:28Speaker 01

  Not really. Don Knuth started to collect examples of graphs coming from various places. So he could 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

• 1:41:50Lex Fridman?

  But there, it's really important and compelling to be able to define a class of graphs.

• 1:41:58Lex Fridman?

  That the, the actual act of defining a class of graphs that you're interested in, it seems to be a, a non-trivial step before talking about instances that we should care about in the real world.

• 1:42:08Speaker 01

  Yeah, it's, there's nothing available there that would be analogous to the training set for supervised learning, you know, where you sort of assume that the world has given you a bunch of examples to work with. We don't really have that for

• 1:42:30Speaker 01

  Problems for combinatorial problems on graphs and networks.

• 1:42:35Lex Fridman?

  You know, there's been a huge growth, a big growth of data sets.

• 1:42:39Speaker 01

  Yeah.

• 1:42:39Lex Fridman?

  Available. Do you think some aspect of theoretical computer science, I might be contradicting my own question while saying it, but will there be some aspect, an empirical aspect of theoretical computer science, which will allow the fact that these data sets are huge, we'll start using them for analysis. Sort of, you know, if you want to say something about a graph algorithm, you might take a net, a social network like Facebook.

• 1:43:10Speaker 01

  Yeah.

• 1:43:10Lex Fridman?

  And looking at subgraphs of that and prove something about the Facebook graph and be respected and at the same time be respected in the theoretical computer science community.

• 1:43:20Speaker 01

  That hasn't been achieved yet, I'm afraid.

• 1:43:23Lex Fridman?

  Is that, is that, is that P equals NP, is that impossible? Is, is it impossible to publish a successful paper in the theoretical computer science community that shows some, some performance on a real world data set? Or is that really just those are two different worlds?

• 1:43:43Speaker 01

  They haven't really come together. I would say that there is a field of experimental algorithms where people, sometimes they're given some family of examples. Sometimes they just generate them at random and they report on performance.

• 1:44:03Speaker 01

  But there's no convincing evidence that the sample is representative of anything at all.

• 1:44:14Lex Fridman?

  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 theoretical computer science?

• 1:44:30Speaker 01

  Well, there are all kinds of relationships among complexity classes that can be studied.

• 1:44:37Speaker 01

  Just to mention one thing, I wrote a paper with Richard Lipton in 1979 where we asked the following question.

• 1:44:51Speaker 01

  If you take a problem, a combinatorial problem in NP, let's say, and you choose, and you pick the size of the problem. Say it's a traveling salesman problem, but of size 52. And you ask, could you get an efficient, a small Boolean circuit tailored for that size, 52, where you could feed the edges of the graph in as Boolean inputs and get as an

• 1:45:33Speaker 01

  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?

• 1:46:13Lex Fridman?

  Just to clarify, small circuits for a problem of particular size? Or even further constraint, small circuit for a particular...

• 1:46:22Speaker 01

  For, no, for all the inputs of that size.

• 1:46:26Lex Fridman?

  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...

• 1:46:35Speaker 01

  That would be, that would be, that would be hard, yeah. But, you know, but there's the existential question. Everybody talks nowadays about every existential questions, existential challenges.

• 1:46:50Lex Fridman?

  Yeah.

• 1:46:51Speaker 01

  You could ask the question, does the Hamiltonian circuit problem have a small circuit for every size? For each size, a different small circuit?

• 1:47:10Speaker 01

  In other words, could you tailor solutions depending on the size and get polynomial size?

• 1:47:17Lex Fridman?

  Even if p is not equal to NP?

• 1:47:19Speaker 01

  Right. And

• 1:47:23Lex Fridman?

  That would be fascinating if that's true.

• 1:47:25Speaker 01

  Yeah. What we proved is that if that were possible, then something strange would happen in complexity theory. Some high level class, which I could briefly describe, something strange would happen. So I'll take a stab at describing what I mean.

• 1:47:48Lex Fridman?

  Sure. Let's go there.

• 1:47:50Speaker 01

  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. So for example, there exists a coloring such that a graph can be colored with

• 1:48:21Speaker 01

  only that number of colors, or there exists a Hamiltonian circuit.

• 1:48:26Lex Fridman?

  There's a statement about this graph.

• 1:48:27Speaker 01

  Yeah. So, so the NP

• 1:48:37Speaker 01

  NP deals with statements of that kind, that there exists a solution.

• 1:48:43Speaker 01

  Now, you could imagine a more complicated expression, which, which says, for all x, there exists a y such that some proposition holds involving both x and y. So that would say, for example, in game theory, for all

• 1:49:09Speaker 01

  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 class, the complexity class, the classes that correspond to those different cases would get bigger and bigger. Or they, they

• 1:49:44Lex Fridman?

  What do you mean by bigger and

• 1:49:45Speaker 01

  Sorry, sorry. They'd get harder and harder to

• 1:49:47Lex Fridman?

  Harder and harder, right.

• 1:49:48Speaker 01

  Harder and harder to solve. And what Lipton and I showed was that if NP had small circuits, then this hierarchy would collapse down to the second level. In other words, you wouldn't get any more mileage by complicating your expressions with three quantifiers, or four quantifiers, or any number.

• 1:50:12Lex Fridman?

  I'm not sure what to make of that exactly.

• 1:50:14Speaker 01

  Well, I think it would be evidence that NP doesn't have small circuits, because something, because something so bizarre would happen. But again, it's only evidence, not proof.

• 1:50:26Lex Fridman?

  Well, yeah, it's not, that's not even evidence, because you're saying P is not equal to NP because something bizarre has to happen. I mean, that's, that's proof by the lack of bizarreness in our science. But it seems like, it seems like just the very notion of P equals NP would be bizarre. So any way you arrive at, there's no way, you have to fight the dragon at some point.

• 1:50:55Speaker 01

  Yeah, okay. Well, anyway, for whatever it's worth, that's what we proved.

• 1:51:00Lex Fridman?

  Awesome. So, so that's a potential space of open, interesting problems.

• 1:51:06Speaker 01

  Yeah.

• 1:51:07Lex Fridman?

  Let me ask you about the, this other world that, of machine learning, of deep learning. What's your thoughts on the history and the current progress of machine learning field that's often progressed sort of separately as a space of ideas and space of people than the theoretical computer science, or just even computer science world?

• 1:51:29Speaker 01

  Yeah, it's really

• 1:51:32Speaker 01

  Very different from the theoretical computer science world because the results about algorithmic performance tend to be empirical. It's more akin to the world of SAT solvers where we observe that for formulas arising in practice, the solver does well. So it's of that type. It's where we're moving into the empirical evaluation of algorithms. Now, it's clear that there have been huge successes in image processing, robotics, natural language processing, a little less so, but across the spectrum of game playing is another one.

• 1:52:17Speaker 01

  There have been great successes. And one of those effects is that it's not too hard to become a millionaire if you can get a reputation in machine learning and there'll be all kinds of companies that will be willing to offer you the moon because they they think that if they have AI at their disposal, then they can solve all kinds of problems. But there are limitations.

• 1:52:52Speaker 01

  One is that the solutions that you get by from to supervised learning problems through convolutional neural networks seem to perform amazingly well, even for inputs that are outside the training set. But we don't have any theoretical understanding of why that's true.

• 1:53:26Speaker 01

  Secondly, the solutions, the networks that you get are very hard to understand. And so very little insight comes out. So, yeah, yeah, they may seem to work on your training set. And you may be able to discover whether your photos occur in a different sample of inputs or not. But we don't really know what's going on. We don't know the features that distinguish the photographs or the objects are not easy to characterize.

• 1:54:06Lex Fridman?

  Well, it's interesting because you mentioned coming up with a small circuit.

• 1:54:10Speaker 01

  Yeah.

• 1:54:10Lex Fridman?

  To solve a particular sized problem.

• 1:54:13Speaker 01

  Yeah.

• 1:54:13Lex Fridman?

  It seems that neural networks are kind of small circuits.

• 1:54:16Speaker 01

  In a way, yeah.

• 1:54:18Lex Fridman?

  But they're not programs, sort of like the things you've designed are algorithms, programs.

• 1:54:23Speaker 01

  Right.

• 1:54:24Lex Fridman?

  Algorithms. Neural networks aren't able to develop algorithms to solve a problem.

• 1:54:31Speaker 01

  Well, they are. They are algorithms. It's just that they're.

• 1:54:37Lex Fridman?

  But sort of, yeah, it's a, it could be a semantic question, but there's not a algorithmic style manipulation of the input. Perhaps you could argue there is.

• 1:54:52Speaker 01

  Yeah, well.

• 1:54:54Lex Fridman?

  It feels a lot more like a function of the input.

• 1:54:57Speaker 01

  It's a, yeah, it's a function. It's a computable function. It's, um, you, once you have the network, you can simulate it on a given input and figure out the output. But what you, you know, if you're, if you're trying to recognize images, then you don't know what features of the image are really. Being determinant of what the circuit is doing. The circuit is sort of very intricate. And it's not clear that the, you know, the simple characteristics that you're looking for,

• 1:55:38Speaker 01

  the edges of the objects, or whatever they may be, they're not emerging from the structure of the circuit.

• 1:55:46Lex Fridman?

  Well, it's not clear to us humans, but it's clear to the circuit.

• 1:55:49Speaker 01

  Yeah, well, right.

• 1:55:51Lex Fridman?

  I mean, it's not clear to sort of the elephant, how the human brain works. But it's clear to us humans, we can explain to each other our reasoning. And that's why the cognitive science, the psychology field exists. Maybe, maybe the whole thing of being explainable to humans is a little bit overrated.

• 1:56:14Speaker 01

  Well, maybe, yeah. I guess, you know, you can say the same thing about our brain, that when we perform acts of cognition, we have no idea how we do it, really.

• 1:56:24Lex Fridman?

  Sure.

• 1:56:25Speaker 01

  We do, though. I mean, we, for, at least for the visual system, the auditory system and so on, we do get some understanding of the principles that they operate under. But for many deeper cognitive tasks, we don't have that.

• 1:56:42Lex Fridman?

  That's right. Let me ask.

• 1:56:44Speaker 01

  Yeah.

• 1:56:45Lex Fridman?

  You've also been doing work on bioinformatics. Does it amaze you that the fundamental building blocks, if we take a step back and look at us humans, that building blocks used by evolution to build us intelligent human beings is all contained there in our DNA?

• 1:57:04Speaker 01

  It's amazing. And what's really amazing is that we have, are beginning to learn how to edit DNA, which is very, very, very fascinating. This.

• 1:57:26Speaker 01

  This ability to take a sequence, find it in the genome and do something to it.

• 1:57:35Lex Fridman?

  I mean, that's really taking our biological systems towards the worlds of algorithms.

• 1:57:41Speaker 01

  Yeah, but it raises a lot of questions.

• 1:57:46Speaker 01

  You have to distinguish between doing it on an individual or doing it on somebody's germ line, which means that all of their descendants will be affected.

• 1:57:57Lex Fridman?

  So that's like an ethical.

• 1:57:59Speaker 01

  Yeah, so it raises very severe ethical questions.

• 1:58:07Speaker 01

  And even doing it on individuals is, there's a lot of hubris involved that you could assume that knocking out a particular gene is going to be beneficial because you don't know what the side effects are going to be. So we have this wonderful new world of gene editing, which is, you know, very, very impressive. And it could be used in agriculture, it could be used in medicine in various ways. But very serious ethical problems arise.

• 1:58:53Lex Fridman?

  But what are to you the most interesting places where algorithms? Sort of the ethical side is an exceptionally challenging thing that I think we're going to have to tackle with all of genetic engineering. But on the algorithmic side, there's a lot of benefit that's possible. So is there areas where you see exciting possibilities for algorithms to help model, optimize, study biological systems?

• 1:59:23Speaker 01

  Yeah, I mean, we can certainly analyze genomic data to figure out which genes are operative in the cell and under what conditions and which proteins affect one another, which proteins physically interact. We can sequence proteins and modify them.

• 1:59:47Lex Fridman?

  Is there some aspect of that that's a computer science problem? Or is that still fundamentally a biology problem?

• 1:59:56Speaker 01

  Well, it's a big data, it's a statistical big data problem for sure. So, you know, the biological data sets are increasing our ability to study our ancestry, to study the tendencies towards disease, to personalize treatment according to what's in our genomes and what tendencies for disease we have, to be able to predict what troubles might come upon us in the future and anticipate

• 2:00:32Speaker 01

  them, to understand whether you, for a woman, whether her proclivity for breast cancer is so strong enough that she would want to take action to avoid it.

• 2:00:54Lex Fridman?

  You dedicate your 1985 Turing Award lecture to the memory of your father. What's your fondest memory of your dad?

• 2:01:10Speaker 01

  Seeing him standing in front of a class at the blackboard, drawing perfect circles by hand, and showing his ability to attract the interest of the motley collection of eighth grade students that he was teaching.

• 2:01:36Lex Fridman?

  When, when did you get a chance to see him draw the perfect circles?

• 2:01:40Speaker 01

  On rare occasions, I would get a chance to sneak into his classroom and observe,

• 2:01:49Speaker 01

  observe it. And I think he was at his best in the classroom. I think he really came to life.

• 2:01:57Speaker 01

  And had fun, not only teaching, but, but, you know, engaging in chit chat with the students and, you know, ingratiating himself with the students. And what I inherited from that is a great desire to be a teacher. I retired recently and a lot of my former students came, students who's with whom I had done research or who had read my papers or who had been in my classes. And when they talked about, about me,

• 2:02:39Speaker 01

  they talked not about my 1979 paper or my 1992 paper, but about what they, what came away in my classes. And not just the details, but just the approach and the, the manner of teaching. And so I sort of take pride in the, at least in my early years as a faculty member at Berkeley. I was exemplary in preparing my lectures and I always came in prepared to the teeth and able therefore to deviate according to what happened in the class and to really,

• 2:03:21Speaker 01

  really provide a model for the students.

• 2:03:25Lex Fridman?

  So is there advice you could give out?

• 2:03:30Lex Fridman?

  For others and how to be a good teacher. So preparation is one thing you've mentioned, being exceptionally well prepared. But are there other things, pieces of advice that you can impart?

• 2:03:41Speaker 01

  Well, the top three would be preparation, preparation, and preparation.

• 2:03:46Lex Fridman?

  Why is preparation so important, I guess?

• 2:03:49Speaker 01

  It's because it gives you the ease to deal with any situation that comes up in the in the classroom and, you know, if you're, if you discover that you're not getting through one way, you can do it another way. If the students have questions, you can handle the questions.

• 2:04:05Lex Fridman?

  Ultimately, you're also feeling the, the, the crowd, the students of what they're struggling with, what they're picking up, just looking at them through the questions, but even just through their eyes.

• 2:04:18Speaker 01

  Yeah.

• 2:04:18Lex Fridman?

  And because of the preparation, you can, you can dance.

• 2:04:22Speaker 01

  You can dance, you can, you can say it another way, give another angle.

• 2:04:28Lex Fridman?

  Are there, in particular, ideas and algorithms of computer science that you find were big aha moments for students where they, for some reason, once they got it, it clicked for them and they fell in love with computer science? Or is it individual, is it different for everybody?

• 2:04:46Speaker 01

  It's different for everybody. You have to work differently with students. Some, some of them just don't, don't need much influence. You, you know, they, they, they're just running with what they're doing and they just need an ear now and then. Others need a little prodding. Others need to be persuaded to collaborate among themselves rather than working alone.

• 2:05:12Speaker 01

  They have their personal ups and downs. So, you know, you have to, have to deal with each student as a human being and bring out the best.

• 2:05:23Lex Fridman?

  Humans are complicated.

• 2:05:25Speaker 01

  Yeah.

• 2:05:26Lex Fridman?

  Perhaps a silly question. If you could relive a moment in your life outside of family because it made you truly happy, or perhaps because it changed the direction of your life in a profound way,

• 2:05:39Lex Fridman?

  what moment would you pick?

• 2:05:41Speaker 01

  I was kind of a lazy student as an undergraduate and even in my first year in graduate school. And I think it was when I started doing research, I had a couple of summer jobs where I was able to contribute. And I had an idea. And then there was one particular course on mathematical methods and operations research, where I just gobbled up the material and I scored 20 points higher than anybody else in the class, then came to the attention of the faculty. And it made me realize that I had some ability that was going somewhere.

• 2:06:22Lex Fridman?

  You realize you're pretty good at this thing. I don't think there's a better way to end it, Richard. It was a huge honor. Thank you for decades of incredible work. Thank you for talking to me.

• 2:06:36Speaker 01

  Thank you. It's been a great pleasure. And you're a superb interviewer.

• 2:06:40Lex Fridman?

  Oh, stop it. Thanks for listening to this conversation with Richard Karp. And thank you to our sponsors, Eight Sleep and Cash App. Please consider supporting this podcast by going to eightsleep.com/lex to check out their awesome mattress and downloading Cash App and using code LEXPODCAST. Click the links, buy the stuff, even just visiting the site, but also considering the purchase helps them know that this podcast is worth supporting in the future. It really is the best way to support this journey I'm on. If you enjoy this thing, subscribe on YouTube, review it with five stars on Apple Podcasts,

• 2:07:21Lex Fridman?

  support it on Patreon, connect with me on Twitter at Lex Fridman, if you can figure out how to spell that. And now let me leave you with some words from Isaac Asimov. I do not fear computers. I fear lack of them. Thank you for listening and hope to see you next time.