Richard Karp is a professor at Berkeley and one of the key 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 signing up with these 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

EPISODE LINKS:
Richard's wikipedia: https://en.wikipedia.org/wiki/Richard_M._Karp

PODCAST INFO:
Podcast website:
https://lexfridman.com/podcast
Apple Podcasts:
https://apple.co/2lwqZIr
Spotify:
https://spoti.fi/2nEwCF8
RSS:
https://lexfridman.com/feed/podcast/
Full episodes playlist:
https://www.youtube.com/playlist?list=PLrAXtmErZgOdP_8GztsuKi9nrraNbKKp4
Clips playlist:
https://www.youtube.com/playlist?list=PLrAXtmErZgOeciFP3CBCIEElOJeitOr41

OUTLINE:
0:00 - Introduction
3:50 - Geometry
9: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

CONNECT:
- Subscribe to this YouTube channel
- Twitter: https://twitter.com/lexfridman
- LinkedIn: https://www.linkedin.com/in/lexfridman
- Facebook: https://www.facebook.com/LexFridmanPage
- Instagram: https://www.instagram.com/lexfridman
- Medium: https://medium.com/@lexfridman
- Support on Patreon: https://www.patreon.com/lexfridman

The following is a conversation with Richard Karp, a professor at Berkeley and 1 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 admirance Karp algorithm for solving the max flow problem on networks, Hopcroft-Karp algorithm for finding maximum cardinality matchings in bipartite graphs, and his landmark paper in complexity theory called Reducibility Among Combinatorial Problems, in which he proved 21 problems to be NP-complete.

This paper was probably the most important catalyst in the explosion of interest in the study of NP-completeness and the P versus NP problem in general.

2 sponsors, Asleep Mattress and Cash App.

Please consider supporting this podcast by going to asleep.com slash Lex and downloading Cash App and using code LEXPODCAST.

It really is the best way to support this podcast.

If you enjoy this thing, subscribe on YouTube, review it with 5 Stars on Apple Podcast, support it on Patreon, or connect with me on Twitter at Lex Friedman.

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 8 Sleep and it's pod pro mattress that you can check out at 8sleep.com slash Lex to get $200 off.

It can cool down to as low as 55 degrees on each side of the bed separately.

Research shows that temperature has a big impact on the quality of our sleep.

Anecdotally, it's been a game changer for me.

I'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 1 of the most important aspects of life, which is sleep, I think has a lot of potential for being beneficial.

The Pod Pro is packed with sensors that track heart rate, heart rate variability, and respiratory rate, showing it all in their app.

The app's health metrics are amazing, but the cooling alone is honestly worth the money.

I don't always sleep, but when I do, I choose the 8Sleep Pod Pro mattress.

Check it out at eightsleep.com slash Lex to get $200 off.

And remember, just visiting the site and considering the purchase helps convince the folks at 8 Sleep that this silly old podcast is worth sponsoring in the future.

This show is also presented by the great and powerful Cash App, the number 1 finance app in the App Store.

Cash App lets you send money to friends, buy Bitcoin, and invest in the stock market with as little as 1 dollar.

It's 1 of the best designed interfaces of an app that I've ever used.

To me, good design is when everything is easy and natural.

Bad design is when the app gets in the way, either because it's buggy or because it tries too hard to be helpful.

I'm looking at you Clippy from Microsoft even though I love you.

Anyway there's a big part of my brain and heart that loves to design things and also to appreciate great design by others.

So again if you get Cash App from the App Store or Google Play and use the code LEXPODCAST, you get $10 and Cash App will also donate $10 to FIRST, an organization that is helping to advance robotics and STEM education for young people around the world.

And now, here's my conversation with Richard

You wrote that at the age of 13, you were first exposed to plane geometry and was wonderstruck by the power and elegance of formal proofs.

Are there problems, proofs, properties, ideas in plane geometry that from that time that you remember being mesmerized by or just enjoying to go through to prove various aspects?

So Michael Rabin 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 2 older students who were studying the problem of finding the shortest distance between 2 non-overlapping circles.

And Michael thought about it and said, you take the straight line between the 2 centers, and the segment between the 2 circles is the shortest, because a straight line is the shortest distance between the 2 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 elegance, that pure reasoning could come up with such a result.

Certainly the shortest distance from the 2 centers of the circles is a straight line.

Could you once again say what's the next step in that proof?

Well, any segment joining the 2 circles, if you extend it by taking the radius on each side, you get a segment with a path with 3 edges, which connects the 2 centers.

And this has to be at least as long as the shortest path, which is the straight line.

So what is it about that elegance that you just find compelling?

Well, just that you could establish a fact about geometry 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.

LRW Was there something about geometry itself, the slightly visual component of it, that you can visualize stuff?

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

You mean being able to visualize three-dimensional objects?

Three-dimensional objects or surfaces, hyperplanes and so on.

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 And it comes as a surprise that that can be done.

Well, it is a surprising idea, I suppose.

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

You start at a corner and draw a line parallel to the opposite side.

And that line sort of trisects the angle between the other 2 sides, and you get a half-plane which has to add up to 180 degrees.

And it consists in 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 3 angles of the triangle.

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.

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.

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

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.

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

What's inside your mind when you're thinking about designing algorithms?

Or even just tackling any mathematical problem?

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

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

Try to take steps that get closer and having the certainty of converging.

So it's basically the mechanics of the algorithm is often very simple.

But especially when you're trying something out on the computer, so for example, 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 optimum.

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

Find the shortest path through a set of cities.

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

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

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

So there's 2 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 2 is proving that this thing is actually going to be pretty good.

Is it in the first sets of intuitions, or is it in the messy details of actually showing that it is going to get to the exact solution and it's gonna run at a certain complexity?

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 finally you hit the optimum.

Perhaps later we'll talk about the assignment problem and I can illustrate.

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.

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.

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

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

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.

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 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 you're 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 entire columns 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.

And so what you have to do 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.

Yeah, the simplicity lies in how you find the, what I oversimplified slightly, what 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 reduce any of the 0 elements, you leave them unchanged.

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

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.

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.

So what do you think about this idea of geeks, as Don Knuth calls them?

What do you think, is it something specific to a mindset that allows you to discover the elegance in computational processes, or is this all of us?

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 1 and doubling the number as long as I could go and testing my memory, my ability to retain the information.

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

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

And the other employee, I was the barker at a skee-ball game.

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

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

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 performing this mental arithmetic.

Some of the most popular videos on the internet is, There's a YouTube channel called Numberphile that shows off different mathematical ideas.

There's still something really profoundly interesting to people about math, the beauty of it.

Something, even if they don't understand the basic concept even being discussed, there's something compelling to it.

Any lessons you drew from your early teen years when you were showing off to your friends with the numbers?

What is it that attracts us to the beauty of mathematics, do you think?

The general population, not just the computer scientists and mathematicians.

You can test whether large numbers are prime.

You can solve little puzzles about cannibals and missionaries.

And at a higher level, the fact that you can do this reasoning, that you can prove in an absolutely ironclad way that some of the angles of a triangle is 180 degrees.

Yeah, it's a nice escape from the messiness of the real world where nothing can be proved.

So, and we'll talk about it, but sometimes the ability to map the real world into such problems where you can't prove it is a powerful step.

Of course, another attribute of geeks is they're not necessarily endowed with emotional intelligence.

And so they can live in a world of abstractions without having to master the complexities of dealing with people.

So just to linger on the historical note, as a PhD student in 1955, you joined the computational lab at Harvard where Howard Aiken had built the Mark I and the Mark IV computers.

Just to take a step back into that history, what were those computers like?

The Mark IV filled a large room, much bigger than this large office that we're talking in now.

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.

So I never used that machine for any practical purpose.

The lab eventually acquired 1 of the earlier commercial computers.

There was already commercial computers in the-

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

And so you had to work hard to allocate the memory properly to also the excess time from 1 word to another depended on the number of the particular words.

And so there was an art to sort of arranging the storage allocation to make fetching data rapid.

Were you attracted to this actual physical world implementation of mathematics?

So it's a mathematical machine that's actually doing the math physically for you?

I think I was attracted to the underlying algorithms.

So could you have imagined, Like what did you imagine was the future of these giant computers?

Could you have imagined that 60 years later we'd have billions of these computers all over the world?

I couldn't imagine that, but there was a sense in the laboratory that this was the wave of the future.

She told me that data processing was going to be really big and I should get into it.

And there was just a feeling that this was going to change the world.

But I didn't think of it in terms of personal computing.

I had no anticipation that we would be walking around with computers in our pockets or anything like that.

Did you see computers as tools, as mathematical mechanisms to analyze sort of theoretical computer science, or is the AI folks, which is an entire other community of dreamers, as something that could 1 day have human level intelligence?

The Turing test, computing and intelligence.

I thought that it wasn't a very good test because it was too subjective.

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

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

That are like strong, reliable, robust across a bunch of different classes of algorithms.

But returning to this emotional mess that is intelligence, do you think it's possible to come up with a test that's as ironclad as some of the computational complexity work?

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

Right, 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?

It seems to me that most of the achievements have 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 physical attributes for exploring their environment.

And I don't see anything in the current achievements of what's called AI that come close to that capability.

I don't think there's any computer program which surpasses a six-month-old child in terms of comprehension of the world.

Do you think this complexity of human intelligence, all the cognitive abilities you have, all the emotion.

Do you think that could be reduced 1 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?

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.

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, that cannot be the way we're eventually going to tackle this problem.

That does not seem like a feasible way to go about it.

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 unless we got enough insight into the operation of the brain.

Do you think, what do you make of consciousness, for example, as an example of something we completely have no clue about?

The fact that we have this subjective experience.

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

Yeah, to know the algorithm, to know itself.

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

See all Lex Fridman transcripts on Youtube

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