Richard Karp: Algorithms and Computational Complexity
AI 与机器学习技术与编程数学音乐与艺术心理与人性
📋 章节目录
暂无章节信息
🔑 关键词
algorithmproblemsalgorithmsdonsizecomputerhardpolynomialgraphparticularsciencecalledcombinatorialmatchinggoingsolutionsolveclassrandomterms
💬 精彩语录
暂无语录
🎙️ 完整对话（2146 条）
Lex Fridman (00:00.000)
The following is a conversation with Richard Karp,
以下是与理查德·卡普的对话，
Lex Fridman (00:02.900)
a professor at Berkeley and one of the most important figures
伯克利大学教授，最重要的人物之一
Lex Fridman (00:06.300)
in the history of theoretical computer science.
在理论计算机科学史上。
Lex Fridman (00:09.480)
In 1985, he received the Turing Award
1985年获得图灵奖
Lex Fridman (00:12.640)
for his research in the theory of algorithms,
表彰他在算法理论方面的研究，
Richard Karp (00:15.120)
including the development of the Admirons Karp algorithm
包括 Admirons Karp 算法的开发
Lex Fridman (00:18.380)
for solving the max flow problem on networks,
为了解决网络上的最大流问题，
Richard Karp (00:21.780)
Hopcroft Karp algorithm for finding maximum cardinality
用于查找最大基数的 Hopcroft Karp 算法
Lex Fridman (00:25.900)
matchings in bipartite graphs,
二分图中的匹配，
Lex Fridman (00:27.960)
and his landmark paper in complexity theory
以及他在复杂性理论方面的里程碑式论文
Lex Fridman (00:30.960)
called Reduceability Among Combinatorial Problems,
称为组合问题的可约化性，
Richard Karp (00:35.260)
in which he proved 21 problems to be NP complete.
其中他证明了 21 个问题是 NP 完全问题。
Lex Fridman (00:38.980)
This paper was probably the most important catalyst
这篇论文可能是最重要的催化剂
Richard Karp (00:41.840)
in the explosion of interest in the study of NP completeness
人们对 NP 完整性研究的兴趣激增
Lex Fridman (00:45.340)
and the P versus NP problem in general.
以及一般的 P 与 NP 问题。
Richard Karp (00:48.760)
Quick summary of the ads.
广告的快速摘要。
Lex Fridman (00:50.180)
Two sponsors, 8sleep mattress and Cash App.
两个赞助商，8sleep 床垫和 Cash App。
Richard Karp (00:53.540)
Please consider supporting this podcast
请考虑支持此播客
Lex Fridman (00:55.640)
by going to 8sleep.com slash Lex
访问 8sleep.com 斜线 Lex
Lex Fridman (00:58.760)
and downloading Cash App and using code LexPodcast.
并下载 Cash App 并使用代码 LexPodcast。
Lex Fridman (01:03.000)
Click the links, buy the stuff.
Richard Karp (01:04.560)
It really is the best way to support this podcast.
Lex Fridman (01:08.040)
If you enjoy this thing, subscribe on YouTube,
Richard Karp (01:10.240)
review it with five stars on Apple Podcast,
Lex Fridman (01:12.440)
support it on Patreon,
Richard Karp (01:13.800)
or connect with me on Twitter at Lex Friedman.
Lex Fridman (01:16.800)
As usual, I'll do a few minutes of ads now
Lex Fridman (01:18.800)
and never any ads in the middle
Lex Fridman (01:20.060)
that can break the flow of the conversation.
Richard Karp (01:22.960)
This show is sponsored by 8sleep and its Pod Pro mattress
Lex Fridman (01:27.340)
that you can check out at 8sleep.com slash Lex
Richard Karp (01:30.680)
to get $200 off.
Lex Fridman (01:32.960)
It controls temperature with an app.
Richard Karp (01:35.880)
It can cool down to as low as 55 degrees
Lex Fridman (01:38.320)
on each side of the bed separately.
Richard Karp (01:41.000)
Research shows that temperature has a big impact
Lex Fridman (01:43.520)
on the quality of our sleep.
Richard Karp (01:45.000)
Anecdotally, it's been a game changer for me.
Lex Fridman (01:47.760)
I love it.
Richard Karp (01:48.760)
It's been a couple of weeks now.
Lex Fridman (01:50.160)
I've just been really enjoying it,
Richard Karp (01:52.480)
both in the fact that I'm getting better sleep
Lex Fridman (01:54.640)
and that it's a smart mattress, essentially.
Richard Karp (01:58.240)
I kind of imagine this being the early days
Lex Fridman (02:00.040)
of artificial intelligence being a part
Richard Karp (02:02.800)
of every aspect of our lives.
Lex Fridman (02:04.320)
And certainly infusing AI in one of the most important
Richard Karp (02:07.440)
aspects of life, which is sleep,
Lex Fridman (02:09.800)
I think has a lot of potential for being beneficial.
Richard Karp (02:13.120)
The Pod Pro is packed with sensors that track heart rate,
Lex Fridman (02:16.440)
heart rate variability, and respiratory rate,
Richard Karp (02:19.480)
showing it all in their app.
Lex Fridman (02:21.760)
The app's health metrics are amazing,
Lex Fridman (02:24.320)
but the cooling alone is honestly worth the money.
Lex Fridman (02:27.120)
I don't always sleep, but when I do,
Richard Karp (02:29.280)
I choose the 8th Sleep Pod Pro mattress.
Lex Fridman (02:31.960)
Check it out at 8thSleep.com slash Lex to get $200 off.
Lex Fridman (02:37.560)
And remember, just visiting the site
Lex Fridman (02:39.040)
and considering the purchase helps convince the folks
Richard Karp (02:42.000)
at 8th Sleep that this silly old podcast
Lex Fridman (02:44.840)
is worth sponsoring in the future.
Richard Karp (02:47.400)
This show is also presented by the great
Lex Fridman (02:50.520)
and powerful Cash App,
Richard Karp (02:53.000)
the number one finance app in the App Store.
Lex Fridman (02:55.320)
When you get it, use code LEXPODCAST.
Richard Karp (02:58.160)
Cash App lets you send money to friends,
Lex Fridman (03:00.120)
buy Bitcoin, and invest in the stock market
Richard Karp (03:02.520)
with as little as $1.
Lex Fridman (03:04.640)
It's one of the best designed interfaces
Richard Karp (03:06.720)
of an app that I've ever used.
Lex Fridman (03:08.480)
To me, good design is when everything is easy and natural.
Richard Karp (03:12.320)
Bad design is when the app gets in the way,
Lex Fridman (03:15.080)
either because it's buggy,
Richard Karp (03:16.560)
or because it tries too hard to be helpful.
Lex Fridman (03:19.280)
I'm looking at you, Clippy, from Microsoft,
Richard Karp (03:21.560)
even though I love you.
Lex Fridman (03:23.160)
Anyway, there's a big part of my brain and heart
Richard Karp (03:25.480)
that loves to design things
Lex Fridman (03:27.400)
and also to appreciate great design by others.
Lex Fridman (03:30.000)
So again, if you get Cash App from the App Store
Lex Fridman (03:32.440)
or Google Play and use the code LEXPODCAST,
Richard Karp (03:35.600)
you get $10, and Cash App will also donate $10 to FIRST,
Lex Fridman (03:39.600)
an organization that is helping to advance
Richard Karp (03:41.800)
robotics and STEM education
Lex Fridman (03:43.480)
for young people around the world.
Lex Fridman (03:45.720)
And now, here's my conversation with Richard Karp.
Lex Fridman (03:50.520)
You wrote that at the age of 13,
Richard Karp (03:52.840)
you were first exposed to plane geometry
Lex Fridman (03:55.240)
and was wonderstruck by the power and elegance
Richard Karp (03:58.280)
of form of proofs.
Lex Fridman (04:00.280)
Are there problems, proofs, properties, ideas
Richard Karp (04:02.640)
in plane geometry that from that time
Lex Fridman (04:04.960)
that you remember being mesmerized by
Lex Fridman (04:07.880)
or just enjoying to go through to prove various aspects?
Lex Fridman (04:12.880)
So Michael Rabin told me this story
Richard Karp (04:16.240)
about an experience he had when he was a young student
Lex Fridman (04:20.360)
who was tossed out of his classroom for bad behavior
Lex Fridman (04:25.200)
and was wandering through the corridors of his school
Lex Fridman (04:29.360)
and came upon two older students
Richard Karp (04:32.560)
who were studying the problem of finding
Lex Fridman (04:35.840)
the shortest distance between two nonoverlapping circles.
Lex Fridman (04:42.920)
And Michael thought about it and said,
Lex Fridman (04:49.120)
you take the straight line between the two centers
Lex Fridman (04:52.360)
and the segment between the two circles is the shortest
Lex Fridman (04:56.080)
because a straight line is the shortest distance
Richard Karp (04:58.600)
between the two centers.
Lex Fridman (05:00.600)
And any other line connecting the circles
Richard Karp (05:03.640)
would be on a longer line.
Lex Fridman (05:07.640)
And I thought, and he thought, and I agreed
Richard Karp (05:10.360)
that this was just elegance, the pure reasoning
Lex Fridman (05:14.600)
could come up with such a result.
Richard Karp (05:17.600)
Certainly the shortest distance
Lex Fridman (05:21.000)
from the two centers of the circles is a straight line.
Lex Fridman (05:25.680)
Could you once again say what's the next step in that proof?
Lex Fridman (05:29.680)
Well, any segment joining the two circles,
Richard Karp (05:36.680)
if you extend it by taking the radius on each side,
Lex Fridman (05:41.440)
you get a path with three edges
Richard Karp (05:46.560)
which connects the two centers.
Lex Fridman (05:49.240)
And this has to be at least as long as the shortest path,
Richard Karp (05:52.560)
which is the straight line.
Lex Fridman (05:53.760)
The straight line, yeah.
Richard Karp (05:54.800)
Wow, yeah, that's quite simple.
Lex Fridman (05:58.480)
So what is it about that elegance
Lex Fridman (06:00.800)
that you just find compelling?
Lex Fridman (06:04.640)
Well, just that you could establish a fact
Richard Karp (06:09.960)
about geometry beyond dispute by pure reasoning.
Lex Fridman (06:18.960)
I also enjoy the challenge of solving puzzles
Richard Karp (06:22.440)
in plain geometry.
Lex Fridman (06:23.400)
It was much more fun than the earlier mathematics courses
Richard Karp (06:27.480)
which were mostly about arithmetic operations
Lex Fridman (06:31.000)
and manipulating them.
Richard Karp (06:32.840)
Was there something about geometry itself,
Lex Fridman (06:35.840)
the slightly visual component of it?
Richard Karp (06:38.160)
Oh, yes, absolutely,
Lex Fridman (06:40.200)
although I lacked three dimensional vision.
Richard Karp (06:44.120)
I wasn't very good at three dimensional vision.
Lex Fridman (06:47.280)
You mean being able to visualize three dimensional objects?
Richard Karp (06:49.680)
Three dimensional objects or surfaces,
Lex Fridman (06:54.280)
hyperplanes and so on.
Lex Fridman (06:57.680)
So there I didn't have an intuition.
Lex Fridman (07:01.680)
But for example, the fact that the sum of the angles
Richard Karp (07:06.960)
of a triangle is 180 degrees is proved convincingly.
Lex Fridman (07:16.200)
And it comes as a surprise that that can be done.
Lex Fridman (07:21.320)
Why is that surprising?
Lex Fridman (07:23.480)
Well, it is a surprising idea, I suppose.
Lex Fridman (07:30.600)
Why is that proved difficult?
Lex Fridman (07:32.400)
It's not, that's the point.
Richard Karp (07:34.200)
It's so easy and yet it's so convincing.
Lex Fridman (07:37.760)
Do you remember what is the proof that it adds up to 180?
Richard Karp (07:42.840)
You start at a corner and draw a line
Lex Fridman (07:47.840)
parallel to the opposite side.
Lex Fridman (07:56.160)
And that line sort of trisects the angle
Lex Fridman (08:02.000)
between the other two sides.
Lex Fridman (08:05.400)
And you get a half plane which has to add up to 180 degrees.
Lex Fridman (08:10.400)
It has to add up to 180 degrees and it consists
Richard Karp (08:15.760)
in the angles by the equality of alternate angles.
Lex Fridman (08:21.680)
What's it called?
Richard Karp (08:24.200)
You get a correspondence between the angles
Lex Fridman (08:27.200)
created along the side of the triangle
Lex Fridman (08:31.960)
and the three angles of the triangle.
Lex Fridman (08:34.680)
Has geometry had an impact on when you look into the future
Lex Fridman (08:38.960)
of your work with combinatorial algorithms?
Lex Fridman (08:41.320)
Has it had some kind of impact in terms of, yeah,
Richard Karp (08:45.240)
being able, the puzzles, the visual aspects
Lex Fridman (08:48.680)
that were first so compelling to you?
Richard Karp (08:51.400)
Not Euclidean geometry particularly.
Lex Fridman (08:54.480)
I think I use tools like linear programming
Lex Fridman (09:00.040)
and integer programming a lot.
Lex Fridman (09:03.000)
But those require high dimensional visualization
Lex Fridman (09:08.000)
and so I tend to go by the algebraic properties.
Lex Fridman (09:13.200)
Right, you go by the linear algebra
Lex Fridman (09:16.640)
and not by the visualization.
Lex Fridman (09:19.560)
Well, the interpretation in terms of, for example,
Richard Karp (09:23.680)
finding the highest point on a polyhedron
Lex Fridman (09:26.360)
as in linear programming is motivating.
Lex Fridman (09:32.640)
But again, I don't have the high dimensional intuition
Lex Fridman (09:37.560)
that would particularly inform me
Lex Fridman (09:40.080)
so I sort of lean on the algebra.
Lex Fridman (09:44.760)
So to linger on that point,
Lex Fridman (09:46.080)
what kind of visualization do you do
Lex Fridman (09:50.960)
when you're trying to think about,
Richard Karp (09:53.240)
we'll get to combinatorial algorithms,
Lex Fridman (09:55.400)
but just algorithms in general.
Richard Karp (09:57.240)
Yeah.
Lex Fridman (09:58.080)
What's inside your mind
Lex Fridman (09:59.760)
when you're thinking about designing algorithms?
Lex Fridman (10:02.240)
Or even just tackling any mathematical problem?
Richard Karp (10:09.440)
Well, I think that usually an algorithm
Lex Fridman (10:12.800)
involves a repetition of some inner loop
Lex Fridman (10:19.200)
and so I can sort of visualize the distance
Lex Fridman (10:24.640)
from the desired solution as iteratively reducing
Richard Karp (10:29.640)
until you finally hit the exact solution.
Lex Fridman (10:33.360)
And try to take steps that get you closer to the.
Richard Karp (10:35.640)
Try to take steps that get closer
Lex Fridman (10:38.160)
and having the certainty of converging.
Lex Fridman (10:41.280)
So it's basically the mechanics of the algorithm
Lex Fridman (10:46.640)
is often very simple,
Lex Fridman (10:49.320)
but especially when you're trying something out
Lex Fridman (10:52.480)
on the computer.
Lex Fridman (10:53.320)
So for example, I did some work
Lex Fridman (10:57.080)
on the traveling salesman problem
Lex Fridman (10:59.000)
and I could see there was a particular function
Lex Fridman (11:03.080)
that had to be minimized
Lex Fridman (11:04.720)
and it was fascinating to see the successive approaches
Lex Fridman (11:08.640)
to the minimum, to the optimum.
Richard Karp (11:11.960)
You mean, so first of all,
Lex Fridman (11:13.040)
traveling salesman problem is where you have to visit
Richard Karp (11:16.360)
every city without ever, the only ones.
Lex Fridman (11:21.320)
Yeah, that's right.
Richard Karp (11:22.480)
Find the shortest path through a set of cities.
Lex Fridman (11:25.120)
Yeah, which is sort of a canonical standard,
Richard Karp (11:28.560)
a really nice problem that's really hard.
Lex Fridman (11:30.480)
Right, exactly, yes.
Lex Fridman (11:32.640)
So can you say again what was nice
Lex Fridman (11:34.520)
about being able to think about the objective function there
Lex Fridman (11:38.440)
and maximizing it or minimizing it?
Lex Fridman (11:41.560)
Well, just that as the algorithm proceeded,
Richard Karp (11:47.120)
you were making progress, continual progress,
Lex Fridman (11:49.680)
and eventually getting to the optimum point.
Lex Fridman (11:54.000)
So there's two parts, maybe.
Lex Fridman (11:57.120)
Maybe you can correct me.
Richard Karp (11:58.400)
First is like getting an intuition
Lex Fridman (12:00.320)
about what the solution would look like
Lex Fridman (12:02.880)
and or even maybe coming up with a solution
Lex Fridman (12:05.560)
and two is proving that this thing
Richard Karp (12:07.280)
is actually going to be pretty good.
Lex Fridman (12:10.880)
What part is harder for you?
Lex Fridman (12:13.600)
Where's the magic happen?
Lex Fridman (12:14.960)
Is it in the first sets of intuitions
Richard Karp (12:17.760)
or is it in the messy details of actually showing
Lex Fridman (12:22.120)
that it is going to get to the exact solution
Lex Fridman (12:25.440)
and it's gonna run at a certain complexity?
Lex Fridman (12:32.360)
Well, the magic is just the fact
Richard Karp (12:34.760)
that the gap from the optimum decreases monotonically
Lex Fridman (12:42.240)
and you can see it happening
Lex Fridman (12:44.480)
and various metrics of what's going on
Lex Fridman (12:48.720)
are improving all along until finally you hit the optimum.
Richard Karp (12:53.680)
Perhaps later we'll talk about the assignment problem
Lex Fridman (12:56.200)
and I can illustrate.
Richard Karp (12:58.480)
It illustrates a little better.
Lex Fridman (13:00.720)
Now zooming out again, as you write,
Richard Karp (13:03.120)
Don Knuth has called attention to a breed of people
Lex Fridman (13:06.880)
who derive great aesthetic pleasure
Richard Karp (13:10.520)
from contemplating the structure of computational processes.
Lex Fridman (13:13.920)
So Don calls these folks geeks
Lex Fridman (13:16.600)
and you write that you remember the moment
Lex Fridman (13:18.600)
you realized you were such a person,
Richard Karp (13:20.680)
you were shown the Hungarian algorithm
Lex Fridman (13:23.120)
to solve the assignment problem.
Lex Fridman (13:25.720)
So perhaps you can explain what the assignment problem is
Lex Fridman (13:29.120)
and what the Hungarian algorithm is.
Lex Fridman (13:33.160)
So in the assignment problem,
Lex Fridman (13:35.440)
you have n boys and n girls
Lex Fridman (13:40.280)
and you are given the desirability of,
Lex Fridman (13:45.280)
or the cost of matching the ith boy
Richard Karp (13:50.200)
with the jth girl for all i and j.
Lex Fridman (13:52.640)
You're given a matrix of numbers
Lex Fridman (13:55.600)
and you want to find the one to one matching
Lex Fridman (14:02.040)
of the boys with the girls
Richard Karp (14:04.280)
such that the sum of the associated costs will be minimized.
Lex Fridman (14:08.720)
So the best way to match the boys with the girls
Richard Karp (14:13.240)
or men with jobs or any two sets.
Lex Fridman (14:16.440)
Any possible matching is possible or?
Richard Karp (14:21.120)
Yeah, all one to one correspondences are permissible.
Lex Fridman (14:26.800)
If there is a connection that is not allowed,
Richard Karp (14:29.440)
then you can think of it as having an infinite cost.
Lex Fridman (14:32.120)
I see, yeah.
Lex Fridman (14:34.320)
So what you do is to depend on the observation
Lex Fridman (14:39.320)
that the identity of the optimal assignment
Richard Karp (14:46.360)
or as we call it, the optimal permutation
Lex Fridman (14:50.760)
is not changed if you subtract a constant
Richard Karp (14:57.640)
from any row or column of the matrix.
Lex Fridman (15:01.640)
You can see that the comparison
Richard Karp (15:03.360)
between the different assignments is not changed by that.
Lex Fridman (15:06.480)
Because if you decrease a particular row,
Richard Karp (15:11.480)
all the elements of a row by some constant,
Lex Fridman (15:14.720)
all solutions decrease by an amount equal to that constant.
Lex Fridman (15:21.120)
So the idea of the algorithm is to start with a matrix
Lex Fridman (15:24.400)
of non negative numbers and keep subtracting
Richard Karp (15:31.240)
from rows or from columns.
Lex Fridman (15:34.240)
Subtracting from rows or entire columns
Richard Karp (15:41.800)
in such a way that you subtract the same constant
Lex Fridman (15:44.800)
from all the elements of that row or column
Richard Karp (15:48.440)
while maintaining the property
Lex Fridman (15:50.760)
that all the elements are non negative.
Richard Karp (15:58.400)
Simple.
Lex Fridman (15:59.280)
Yeah, and so what you have to do
Richard Karp (16:04.720)
is find small moves which will decrease the total cost
Lex Fridman (16:13.440)
while subtracting constants from rows or columns.
Lex Fridman (16:17.600)
And there's a particular way of doing that
Lex Fridman (16:19.480)
by computing the kind of shortest path
Richard Karp (16:22.200)
through the elements in the matrix.
Lex Fridman (16:24.000)
And you just keep going in this way
Richard Karp (16:28.480)
until you finally get a full permutation of zeros
Lex Fridman (16:33.240)
while the matrix is non negative
Lex Fridman (16:34.920)
and then you know that that has to be the cheapest.
Lex Fridman (16:38.520)
Is that as simple as it sounds?
Lex Fridman (16:42.560)
So the shortest path of the matrix part.
Lex Fridman (16:45.560)
Yeah, the simplicity lies in how you find,
Richard Karp (16:48.880)
I oversimplified slightly what you,
Lex Fridman (16:53.280)
you will end up subtracting a constant
Richard Karp (16:56.440)
from some rows or columns
Lex Fridman (16:59.120)
and adding the same constant back to other rows and columns.
Lex Fridman (17:04.200)
So as not to reduce any of the zero elements,
Lex Fridman (17:09.160)
you leave them unchanged.
Lex Fridman (17:11.080)
But each individual step modifies several rows and columns
Lex Fridman (17:22.440)
by the same amount but overall decreases the cost.
Lex Fridman (17:26.600)
So there's something about that elegance
Lex Fridman (17:29.800)
that made you go aha, this is a beautiful,
Richard Karp (17:32.240)
like it's amazing that something like this,
Lex Fridman (17:35.680)
something so simple can solve a problem like this.
Richard Karp (17:38.080)
Yeah, it's really cool.
Lex Fridman (17:39.760)
If I had mechanical ability,
Richard Karp (17:42.280)
I would probably like to do woodworking
Lex Fridman (17:44.760)
or other activities where you sort of shape something
Richard Karp (17:51.440)
into something beautiful and orderly
Lex Fridman (17:55.440)
and there's something about the orderly systematic nature
Richard Karp (18:00.560)
of that iterative algorithm that is pleasing to me.
Lex Fridman (18:05.520)
So what do you think about this idea of geeks
Lex Fridman (18:09.000)
as Don Knuth calls them?
Lex Fridman (18:11.320)
What do you think, is it something specific to a mindset
Richard Karp (18:16.520)
that allows you to discover the elegance
Lex Fridman (18:19.880)
in computational processes or is this all of us,
Lex Fridman (18:23.160)
can all of us discover this beauty?
Lex Fridman (18:25.280)
Were you born this way?
Richard Karp (18:28.480)
I think so.
Lex Fridman (18:29.320)
I always like to play with numbers.
Richard Karp (18:30.760)
I used to amuse myself by multiplying
Lex Fridman (18:35.760)
by multiplying four digit decimal numbers in my head
Lex Fridman (18:40.320)
and putting myself to sleep by starting with one
Lex Fridman (18:44.440)
and doubling the number as long as I could go
Lex Fridman (18:48.160)
and testing my memory, my ability to retain the information.
Lex Fridman (18:52.720)
And I also read somewhere that you wrote
Richard Karp (18:55.920)
that you enjoyed showing off to your friends
Lex Fridman (18:59.880)
by I believe multiplying four digit numbers.
Richard Karp (19:04.600)
Right.
Lex Fridman (19:05.440)
Four digit numbers.
Richard Karp (19:07.040)
Yeah, I had a summer job at a beach resort
Lex Fridman (19:10.760)
outside of Boston and the other employee,
Richard Karp (19:16.720)
I was the barker at a skee ball game.
Lex Fridman (19:20.160)
Yeah.
Richard Karp (19:21.000)
I used to sit at a microphone saying come one,
Lex Fridman (19:26.240)
come all, come in and play skee ball,
Richard Karp (19:28.200)
five cents to play, a nickel to win and so on.
Lex Fridman (19:31.040)
That's what a barker, I wasn't sure if I should know
Lex Fridman (19:33.840)
but barker, that's, so you're the charming,
Lex Fridman (19:38.240)
outgoing person that's getting people to come in.
Richard Karp (19:41.200)
Yeah, well I wasn't particularly charming
Lex Fridman (19:43.560)
but I could be very repetitious and loud.
Lex Fridman (19:47.120)
And the other employees were sort of juvenile delinquents
Lex Fridman (19:53.640)
who had no academic bent but somehow I found
Richard Karp (19:58.640)
that I could impress them by performing
Lex Fridman (1:00:04.000)
to the P equals NP question
Richard Karp (1:00:06.800)
because all it takes is to show that one algorithm
Lex Fridman (1:00:10.600)
in this class.
Lex Fridman (1:00:11.440)
So the P versus NP can be re expressed
Lex Fridman (1:00:13.760)
as simply asking whether the satisfiability problem
Richard Karp (1:00:17.600)
of propositional logic is solvable in polynomial time.
Lex Fridman (1:00:23.520)
But there's more.
Richard Karp (1:00:28.000)
I encountered Cook's paper
Lex Fridman (1:00:30.360)
when he published it in a conference in 1971.
Richard Karp (1:00:34.600)
Yeah, so when I saw Cook's paper
Lex Fridman (1:00:37.760)
and saw this reduction of each of the problems in NP
Richard Karp (1:00:44.440)
by a uniform method to the satisfiability problem
Lex Fridman (1:00:49.200)
of propositional logic,
Richard Karp (1:00:52.600)
that meant that the satisfiability problem
Lex Fridman (1:00:54.600)
was a universal combinatorial problem.
Lex Fridman (1:00:59.320)
And it occurred to me through experience I had had
Lex Fridman (1:01:04.160)
in trying to solve other combinatorial problems
Richard Karp (1:01:07.760)
that there were many other problems
Lex Fridman (1:01:10.440)
which seemed to have that universal structure.
Lex Fridman (1:01:16.040)
And so I began looking for reductions
Lex Fridman (1:01:21.600)
from the satisfiability to other problems.
Lex Fridman (1:01:26.080)
And one of the other problems
Lex Fridman (1:01:31.760)
would be the so called integer programming problem
Richard Karp (1:01:35.680)
of determining whether there's a solution
Lex Fridman (1:01:40.280)
to a set of linear inequalities involving integer variables.
Richard Karp (1:01:48.200)
Just like linear programming,
Lex Fridman (1:01:49.560)
but there's a constraint that the variables
Richard Karp (1:01:51.720)
must remain integers.
Lex Fridman (1:01:53.640)
In fact, must be the zero or one
Richard Karp (1:01:56.400)
could only take on those values.
Lex Fridman (1:01:58.520)
And that makes the problem much harder.
Richard Karp (1:02:00.800)
Yes, that makes the problem much harder.
Lex Fridman (1:02:03.680)
And it was not difficult to show
Richard Karp (1:02:07.360)
that the satisfiability problem can be restated
Lex Fridman (1:02:11.640)
as an integer programming problem.
Lex Fridman (1:02:13.880)
So can you pause on that?
Lex Fridman (1:02:15.200)
Was that one of the first mappings that you tried to do?
Lex Fridman (1:02:19.080)
And how hard is that mapping?
Lex Fridman (1:02:20.440)
You said it wasn't hard to show,
Lex Fridman (1:02:21.760)
but that's a big leap.
Lex Fridman (1:02:27.440)
It is a big leap, yeah.
Richard Karp (1:02:29.360)
Well, let me give you another example.
Lex Fridman (1:02:32.960)
Another problem in NP
Richard Karp (1:02:35.160)
is whether a graph contains a clique of a given size.
Lex Fridman (1:02:42.960)
And now the question is,
Richard Karp (1:02:47.960)
can we reduce the propositional logic problem
Lex Fridman (1:02:51.200)
to the problem of whether there's a clique
Lex Fridman (1:02:55.480)
of a certain size?
Lex Fridman (1:02:58.720)
Well, if you look at the propositional logic problem,
Richard Karp (1:03:01.280)
it can be expressed as a number of clauses,
Lex Fridman (1:03:05.560)
each of which is a,
Richard Karp (1:03:11.080)
of the form A or B or C,
Lex Fridman (1:03:15.360)
where A is either one of the variables in the problem
Richard Karp (1:03:18.360)
or the negation of one of the variables.
Lex Fridman (1:03:22.600)
And an instance of the propositional logic problem
Richard Karp (1:03:30.200)
can be rewritten using operations of Boolean logic,
Lex Fridman (1:03:37.000)
can be rewritten as the conjunction of a set of clauses,
Richard Karp (1:03:41.280)
the AND of a set of ORs,
Lex Fridman (1:03:43.680)
where each clause is a disjunction, an OR of variables
Richard Karp (1:03:49.600)
or negated variables.
Lex Fridman (1:03:53.880)
So the question in the satisfiability problem
Richard Karp (1:04:01.200)
is whether those clauses can be simultaneously satisfied.
Lex Fridman (1:04:07.160)
Now, to satisfy all those clauses,
Richard Karp (1:04:09.080)
you have to find one of the terms in each clause,
Lex Fridman (1:04:13.920)
which is going to be true in your truth assignment,
Lex Fridman (1:04:20.800)
but you can't make the same variable both true and false.
Lex Fridman (1:04:24.680)
So if you have the variable A in one clause
Lex Fridman (1:04:29.600)
and you want to satisfy that clause by making A true,
Lex Fridman (1:04:34.240)
you can't also make the complement of A true
Richard Karp (1:04:38.360)
in some other clause.
Lex Fridman (1:04:39.720)
And so the goal is to make every single clause true
Richard Karp (1:04:43.080)
if it's possible to satisfy this,
Lex Fridman (1:04:45.200)
and the way you make it true is at least...
Richard Karp (1:04:48.840)
One term in the clause must be true.
Lex Fridman (1:04:52.480)
Got it.
Lex Fridman (1:04:53.920)
So now we, to convert this problem
Lex Fridman (1:04:58.400)
to something called the independent set problem,
Richard Karp (1:05:01.160)
where you're just sort of asking for a set of vertices
Lex Fridman (1:05:06.160)
in a graph such that no two of them are adjacent,
Richard Karp (1:05:08.840)
sort of the opposite of the clique problem.
Lex Fridman (1:05:14.920)
So we've seen that we can now express that as
Richard Karp (1:05:24.760)
finding a set of terms, one in each clause,
Lex Fridman (1:05:29.760)
without picking both the variable
Lex Fridman (1:05:33.440)
and the negation of that variable,
Lex Fridman (1:05:36.200)
because if the variable is assigned the truth value,
Richard Karp (1:05:40.000)
the negated variable has to have the opposite truth value.
Lex Fridman (1:05:44.080)
And so we can construct a graph where the vertices
Richard Karp (1:05:49.400)
are the terms in all of the clauses,
Lex Fridman (1:05:54.400)
and you have an edge between two terms
Richard Karp (1:06:07.720)
if an edge between two occurrences of terms,
Lex Fridman (1:06:14.480)
either if they're both in the same clause,
Richard Karp (1:06:16.720)
because you're only picking one element from each clause,
Lex Fridman (1:06:20.320)
and also an edge between them if they represent
Richard Karp (1:06:23.680)
opposite values of the same variable,
Lex Fridman (1:06:26.160)
because you can't make a variable both true and false.
Lex Fridman (1:06:29.560)
And so you get a graph where you have
Lex Fridman (1:06:31.880)
all of these occurrences of variables,
Richard Karp (1:06:34.360)
you have edges, which mean that you're not allowed
Lex Fridman (1:06:37.840)
to choose both ends of the edge,
Richard Karp (1:06:41.120)
either because they're in the same clause
Lex Fridman (1:06:43.160)
or they're negations of one another.
Richard Karp (1:06:46.360)
All right, and that's a, first of all, sort of to zoom out,
Lex Fridman (1:06:50.520)
that's a really powerful idea that you can take a graph
Lex Fridman (1:06:55.240)
and connect it to a logic equation somehow,
Lex Fridman (1:07:00.240)
and do that mapping for all possible formulations
Richard Karp (1:07:04.240)
of a particular problem on a graph.
Lex Fridman (1:07:06.440)
Yeah.
Richard Karp (1:07:07.280)
I mean, that still is hard for me to believe.
Lex Fridman (1:07:12.280)
Yeah, it's hard for me to believe.
Richard Karp (1:07:14.400)
It's hard for me to believe that that's possible.
Lex Fridman (1:07:17.800)
That they're, like, what do you make of that,
Richard Karp (1:07:20.840)
that there's such a union of,
Lex Fridman (1:07:24.840)
there's such a friendship among all these problems across
Richard Karp (1:07:28.800)
that somehow are akin to combinatorial algorithms,
Lex Fridman (1:07:33.880)
that they're all somehow related?
Richard Karp (1:07:35.920)
I know it can be proven, but what do you make of it,
Lex Fridman (1:07:39.960)
that that's true?
Richard Karp (1:07:41.720)
Well, that they just have the same expressive power.
Lex Fridman (1:07:46.800)
You can take any one of them
Lex Fridman (1:07:49.600)
and translate it into the terms of the other.
Lex Fridman (1:07:53.520)
The fact that they have the same expressive power
Richard Karp (1:07:55.600)
also somehow means that they can be translatable.
Lex Fridman (1:07:59.040)
Right, and what I did in the 1971 paper
Richard Karp (1:08:03.560)
was to take 21 fundamental problems,
Lex Fridman (1:08:08.560)
the commonly occurring problems of packing,
Richard Karp (1:08:12.400)
covering, matching, and so forth,
Lex Fridman (1:08:15.920)
lying in the class NP,
Lex Fridman (1:08:19.280)
and show that the satisfiability problem
Lex Fridman (1:08:21.920)
can be reexpressed as any of those,
Richard Karp (1:08:24.320)
that any of those have the same expressive power.
Lex Fridman (1:08:30.040)
And that was like throwing down the gauntlet
Richard Karp (1:08:32.000)
of saying there's probably many more problems like this.
Lex Fridman (1:08:35.920)
Right.
Richard Karp (1:08:36.760)
Saying that, look, that they're all the same.
Lex Fridman (1:08:39.680)
They're all the same, but not exactly.
Richard Karp (1:08:43.160)
They're all the same in terms of whether they are
Lex Fridman (1:08:49.000)
rich enough to express any of the others.
Lex Fridman (1:08:53.760)
But that doesn't mean that they have
Lex Fridman (1:08:55.320)
the same computational complexity.
Lex Fridman (1:08:57.800)
But what we can say is that either all of these problems
Lex Fridman (1:09:02.280)
or none of them are solvable in polynomial time.
Richard Karp (1:09:05.880)
Yeah, so what is NP completeness
Lex Fridman (1:09:08.360)
and NP hard as classes?
Richard Karp (1:09:11.120)
Oh, that's just a small technicality.
Lex Fridman (1:09:14.080)
So when we're talking about decision problems,
Richard Karp (1:09:17.320)
that means that the answer is just yes or no.
Lex Fridman (1:09:21.000)
There is a clique of size 15
Richard Karp (1:09:23.360)
or there's not a clique of size 15.
Lex Fridman (1:09:26.800)
On the other hand, an optimization problem
Richard Karp (1:09:28.920)
would be asking find the largest clique.
Lex Fridman (1:09:33.200)
The answer would not be yes or no.
Richard Karp (1:09:35.040)
It would be 15.
Lex Fridman (1:09:39.600)
So when you're asking for the,
Richard Karp (1:09:42.960)
when you're putting a valuation on the different solutions
Lex Fridman (1:09:46.680)
and you're asking for the one with the highest valuation,
Richard Karp (1:09:49.120)
that's an optimization problem.
Lex Fridman (1:09:51.440)
And there's a very close affinity
Richard Karp (1:09:52.920)
between the two kinds of problems.
Lex Fridman (1:09:55.480)
But the counterpart of being the hardest decision problem,
Richard Karp (1:10:02.360)
the hardest yes, no problem,
Lex Fridman (1:10:04.280)
the counterpart of that is to minimize
Richard Karp (1:10:09.920)
or maximize an objective function.
Lex Fridman (1:10:13.440)
And so a problem that's hardest in the class
Richard Karp (1:10:17.400)
when viewed in terms of optimization,
Lex Fridman (1:10:19.960)
those are called NP hard rather than NP complete.
Lex Fridman (1:10:24.480)
And NP complete is for decision problems.
Lex Fridman (1:10:26.280)
And NP complete is for decision problems.
Lex Fridman (1:10:28.740)
So if somebody shows that P equals NP,
Lex Fridman (1:10:35.620)
what do you think that proof will look like
Richard Karp (1:10:39.460)
if you were to put on yourself,
Lex Fridman (1:10:41.540)
if it's possible to show that as a proof
Lex Fridman (1:10:45.340)
or to demonstrate an algorithm?
Lex Fridman (1:10:49.100)
All I can say is that it will involve concepts
Richard Karp (1:10:52.260)
that we do not now have and approaches that we don't have.
Lex Fridman (1:10:56.420)
Do you think those concepts are out there
Richard Karp (1:10:58.620)
in terms of inside complexity theory,
Lex Fridman (1:11:02.000)
inside of computational analysis of algorithms?
Lex Fridman (1:11:04.780)
Do you think there's concepts
Lex Fridman (1:11:05.860)
that are totally outside of the box
Lex Fridman (1:11:07.940)
that we haven't considered yet?
Lex Fridman (1:11:09.180)
I think that if there is a proof that P is equal to NP
Richard Karp (1:11:13.180)
or that P is unequal to NP,
Lex Fridman (1:11:17.820)
it'll depend on concepts that are now outside the box.
Richard Karp (1:11:22.320)
Now, if that's shown either way, P equals NP or P not,
Lex Fridman (1:11:25.940)
well, actually P equals NP,
Lex Fridman (1:11:28.260)
what impact, you kind of mentioned a little bit,
Lex Fridman (1:11:32.260)
but can you linger on it?
Lex Fridman (1:11:34.140)
What kind of impact would it have
Lex Fridman (1:11:36.780)
on theoretical computer science
Lex Fridman (1:11:38.340)
and perhaps software based systems in general?
Lex Fridman (1:11:42.220)
Well, I think it would have enormous impact on the world
Richard Karp (1:11:46.260)
in either way case.
Lex Fridman (1:11:49.180)
If P is unequal to NP, which is what we expect,
Richard Karp (1:11:53.280)
then we know that for the great majority
Lex Fridman (1:11:56.860)
of the combinatorial problems that come up,
Richard Karp (1:11:59.500)
since they're known to be NP complete,
Lex Fridman (1:12:02.940)
we're not going to be able to solve them
Richard Karp (1:12:05.060)
by efficient algorithms.
Lex Fridman (1:12:07.780)
However, there's a little bit of hope
Richard Karp (1:12:11.620)
in that it may be that we can solve most instances.
Lex Fridman (1:12:16.560)
All we know is that if a problem is not NP,
Richard Karp (1:12:19.860)
then it can't be solved efficiently on all instances.
Lex Fridman (1:12:22.920)
But basically, if we find that P is unequal to NP,
Richard Karp (1:12:32.720)
it will mean that we can't expect always
Lex Fridman (1:12:35.320)
to get the optimal solutions to these problems.
Lex Fridman (1:12:38.680)
And we have to depend on heuristics
Lex Fridman (1:12:41.040)
that perhaps work most of the time
Richard Karp (1:12:43.160)
or give us good approximate solutions, but not.
Lex Fridman (1:12:47.160)
So we would turn our eye towards the heuristics
Richard Karp (1:12:51.760)
with a little bit more acceptance and comfort on our hearts.
Lex Fridman (1:12:56.400)
Exactly.
Richard Karp (1:12:57.560)
Okay, so let me ask a romanticized question.
Lex Fridman (1:13:02.100)
What to you is one of the most
Richard Karp (1:13:04.480)
or the most beautiful combinatorial algorithm
Lex Fridman (1:13:08.180)
in your own life or just in general in the field
Lex Fridman (1:13:10.880)
that you've ever come across or have developed yourself?
Lex Fridman (1:13:14.080)
Oh, I like the stable matching problem
Richard Karp (1:13:17.760)
or the stable marriage problem very much.
Lex Fridman (1:13:22.760)
What's the stable matching problem?
Richard Karp (1:13:25.120)
Yeah.
Lex Fridman (1:13:26.400)
Imagine that you want to marry off N boys with N girls.
Lex Fridman (1:13:37.120)
And each boy has an ordered list
Lex Fridman (1:13:39.900)
of his preferences among the girls.
Richard Karp (1:13:42.320)
His first choice, his second choice,
Lex Fridman (1:13:44.760)
through her, Nth choice.
Lex Fridman (1:13:47.400)
And each girl also has an ordering of the boys,
Lex Fridman (1:13:55.400)
his first choice, second choice, and so on.
Lex Fridman (1:13:58.880)
And we'll say that a matching,
Lex Fridman (1:14:03.480)
a one to one matching of the boys with the girls is stable
Richard Karp (1:14:07.560)
if there are no two couples in the matching
Lex Fridman (1:14:15.120)
such that the boy in the first couple
Richard Karp (1:14:18.640)
prefers the girl in the second couple to her mate
Lex Fridman (1:14:23.200)
and she prefers the boy to her current mate.
Richard Karp (1:14:27.040)
In other words, if the matching is stable
Lex Fridman (1:14:31.280)
if there is no pair who want to run away with each other
Richard Karp (1:14:35.440)
leaving their partners behind.
Lex Fridman (1:14:38.760)
Gosh, yeah.
Richard Karp (1:14:39.600)
Yeah.
Lex Fridman (1:14:44.920)
Actually, this is relevant to matching residents
Richard Karp (1:14:49.100)
with hospitals and some other real life problems,
Lex Fridman (1:14:52.280)
although not quite in the form that I described.
Lex Fridman (1:14:56.960)
So it turns out that there is,
Lex Fridman (1:15:00.480)
for any set of preferences, a stable matching exists.
Lex Fridman (1:15:06.000)
And moreover, it can be computed
Lex Fridman (1:15:11.000)
by a simple algorithm
Richard Karp (1:15:14.040)
in which each boy starts making proposals to girls.
Lex Fridman (1:15:21.000)
And if the girl receives the proposal,
Richard Karp (1:15:23.940)
she accepts it tentatively,
Lex Fridman (1:15:25.920)
but she can drop it later
Richard Karp (1:15:32.800)
if she gets a better proposal from her point of view.
Lex Fridman (1:15:36.720)
And the boys start going down their lists
Richard Karp (1:15:39.000)
proposing to their first, second, third choices
Lex Fridman (1:15:41.980)
until stopping when a proposal is accepted.
Lex Fridman (1:15:50.400)
But the girls meanwhile are watching the proposals
Lex Fridman (1:15:53.360)
that are coming into them.
Lex Fridman (1:15:55.380)
And the girl will drop her current partner
Lex Fridman (1:16:01.080)
if she gets a better proposal.
Lex Fridman (1:16:03.520)
And the boys never go back through the list?
Lex Fridman (1:16:06.280)
They never go back, yeah.
Lex Fridman (1:16:07.600)
So once they've been denied.
Lex Fridman (1:16:11.720)
They don't try again.
Richard Karp (1:16:12.800)
They don't try again
Lex Fridman (1:16:14.640)
because the girls are always improving their status
Richard Karp (1:16:19.240)
as they receive better and better proposals.
Lex Fridman (1:16:22.800)
The boys are going down their lists starting
Richard Karp (1:16:25.560)
with their top preferences.
Lex Fridman (1:16:28.600)
And one can prove that the process will come to an end
Richard Karp (1:16:39.540)
where everybody will get matched with somebody
Lex Fridman (1:16:43.440)
and you won't have any pair
Richard Karp (1:16:46.520)
that want to abscond from each other.
Lex Fridman (1:16:50.360)
Do you find the proof or the algorithm itself beautiful?
Richard Karp (1:16:54.120)
Or is it the fact that with the simplicity
Lex Fridman (1:16:56.720)
of just the two marching,
Richard Karp (1:16:59.560)
I mean the simplicity of the underlying rule
Lex Fridman (1:17:01.760)
of the algorithm, is that the beautiful part?
Richard Karp (1:17:04.820)
Both I would say.
Lex Fridman (1:17:07.560)
And you also have the observation that you might ask
Richard Karp (1:17:11.760)
who is better off, the boys who are doing the proposing
Lex Fridman (1:17:14.680)
or the girls who are reacting to proposals.
Lex Fridman (1:17:17.760)
And it turns out that it's the boys
Lex Fridman (1:17:20.080)
who are doing the best.
Richard Karp (1:17:22.920)
That is, each boy is doing at least as well
Lex Fridman (1:17:25.840)
as he could do in any other staple matching.
Lex Fridman (1:17:30.480)
So there's a sort of lesson for the boys
Lex Fridman (1:17:33.180)
that you should go out and be proactive
Lex Fridman (1:17:36.080)
and make those proposals.
Lex Fridman (1:17:38.680)
Go for broke.
Richard Karp (1:17:41.160)
I don't know if this is directly mappable philosophically
Lex Fridman (1:17:44.280)
to our society, but certainly seems
Richard Karp (1:17:46.800)
like a compelling notion.
Lex Fridman (1:17:48.160)
And like you said, there's probably a lot
Richard Karp (1:17:51.360)
of actual real world problems that this could be mapped to.
Lex Fridman (1:17:54.600)
Yeah, well you get complications.
Richard Karp (1:17:58.600)
For example, what happens when a husband and wife
Lex Fridman (1:18:01.500)
want to be assigned to the same hospital?
Lex Fridman (1:18:03.720)
So you have to take those constraints into account.
Lex Fridman (1:18:10.520)
And then the problem becomes NP hard.
Lex Fridman (1:18:15.920)
Why is it a problem for the husband and wife
Lex Fridman (1:18:18.040)
to be assigned to the same hospital?
Richard Karp (1:18:20.000)
No, it's desirable.
Lex Fridman (1:18:22.480)
Or at least go to the same city.
Lex Fridman (1:18:24.080)
So you can't, if you're assigning residents to hospitals.
Lex Fridman (1:18:29.560)
And then you have some preferences
Richard Karp (1:18:32.080)
for the husband and the wife or for the hospitals.
Lex Fridman (1:18:34.600)
The residents have their own preferences.
Richard Karp (1:18:39.920)
Residents both male and female have their own preferences.
Lex Fridman (1:18:44.760)
The hospitals have their preferences.
Lex Fridman (1:18:47.720)
But if resident A, the boy, is going to Philadelphia,
Lex Fridman (1:18:55.960)
then you'd like his wife also to be assigned
Richard Karp (1:19:01.720)
to a hospital in Philadelphia.
Lex Fridman (1:19:04.440)
Which step makes it a NP hard problem that you mentioned?
Richard Karp (1:19:08.000)
The fact that you have this additional constraint.
Lex Fridman (1:19:11.120)
That it's not just the preferences of individuals,
Lex Fridman (1:19:15.000)
but the fact that the two partners to a marriage
Lex Fridman (1:19:19.840)
have to be assigned to the same place.
Richard Karp (1:19:22.880)
I'm being a little dense.
Lex Fridman (1:19:29.320)
The perfect matching, no, not the perfect,
Richard Karp (1:19:31.600)
stable matching is what you referred to.
Lex Fridman (1:19:33.880)
That's when two partners are trying to.
Richard Karp (1:19:36.160)
Okay, what's confusing you is that in the first
Lex Fridman (1:19:39.280)
interpretation of the problem,
Richard Karp (1:19:40.740)
I had boys matching with girls.
Lex Fridman (1:19:42.900)
Yes.
Richard Karp (1:19:44.220)
In the second interpretation,
Lex Fridman (1:19:46.540)
you have humans matching with institutions.
Richard Karp (1:19:49.660)
With institutions.
Lex Fridman (1:19:51.100)
I, and there's a coupling between within the,
Richard Karp (1:19:54.380)
gotcha, within the humans.
Lex Fridman (1:19:56.020)
Yeah.
Richard Karp (1:19:56.860)
Any added little constraint will make it an NP hard problem.
Lex Fridman (1:20:00.420)
Well, yeah.
Richard Karp (1:20:03.440)
Okay.
Lex Fridman (1:20:05.060)
By the way, the algorithm you mentioned
Lex Fridman (1:20:06.220)
wasn't one of yours or no?
Lex Fridman (1:20:07.860)
No, no, that was due to Gale and Shapley
Lex Fridman (1:20:11.420)
and my friend David Gale passed away
Lex Fridman (1:20:15.500)
before he could get part of a Nobel Prize,
Lex Fridman (1:20:18.060)
but his partner Shapley shared in a Nobel Prize
Lex Fridman (1:20:22.780)
with somebody else for.
Lex Fridman (1:20:24.340)
Economics?
Lex Fridman (1:20:25.180)
For economics.
Richard Karp (1:20:28.460)
For ideas stemming from the stable matching idea.
Lex Fridman (1:20:32.580)
So you've also have developed yourself
Richard Karp (1:20:35.220)
some elegant, beautiful algorithms.
Lex Fridman (1:20:38.260)
Again, picking your children,
Lex Fridman (1:20:39.720)
so the Robin Karp algorithm for string searching,
Lex Fridman (1:20:43.380)
pattern matching, Edmund Karp algorithm for max flows
Richard Karp (1:20:46.220)
we mentioned, Hopcroft Karp algorithm for finding
Lex Fridman (1:20:49.060)
maximum cardinality matchings in bipartite graphs.
Richard Karp (1:20:52.180)
Is there ones that stand out to you,
Lex Fridman (1:20:55.460)
ones you're most proud of or just
Richard Karp (1:20:59.460)
whether it's beauty, elegance,
Lex Fridman (1:21:01.740)
or just being the right discovery development
Lex Fridman (1:21:06.420)
in your life that you're especially proud of?
Lex Fridman (1:21:10.100)
I like the Rabin Karp algorithm
Richard Karp (1:21:12.180)
because it illustrates the power of randomization.
Lex Fridman (1:21:17.540)
So the problem there
Richard Karp (1:21:23.100)
is to decide whether a given long string of symbols
Lex Fridman (1:21:28.100)
is to decide whether a given long string of symbols
Richard Karp (1:21:34.340)
from some alphabet contains a given word,
Lex Fridman (1:21:39.260)
whether a particular word occurs
Richard Karp (1:21:41.500)
within some very much longer word.
Lex Fridman (1:21:45.500)
And so the idea of the algorithm
Richard Karp (1:21:52.340)
is to associate with the word that we're looking for,
Lex Fridman (1:21:57.220)
a fingerprint, some number,
Richard Karp (1:22:02.820)
or some combinatorial object that describes that word,
Lex Fridman (1:22:10.380)
and then to look for an occurrence of that same fingerprint
Richard Karp (1:22:13.580)
as you slide along the longer word.
Lex Fridman (1:22:18.540)
And what we do is we associate with each word a number.
Lex Fridman (1:22:23.540)
So first of all, we think of the letters
Lex Fridman (1:22:26.540)
that occur in a word as the digits of, let's say,
Richard Karp (1:22:30.980)
decimal or whatever base here,
Lex Fridman (1:22:36.780)
whatever number of different symbols there are.
Richard Karp (1:22:40.020)
That's the base of the numbers, yeah.
Lex Fridman (1:22:42.340)
Right, so every word can then be thought of as a number
Richard Karp (1:22:46.140)
with the letters being the digits of that number.
Lex Fridman (1:22:50.340)
And then we pick a random prime number in a certain range,
Lex Fridman (1:22:55.540)
and we take that word viewed as a number,
Lex Fridman (1:23:00.060)
and take the remainder on dividing that number by the prime.
Lex Fridman (1:23:09.580)
So coming up with a nice hash function.
Lex Fridman (1:23:11.820)
It's a kind of hash function.
Richard Karp (1:23:13.660)
Yeah, it gives you a little shortcut
Lex Fridman (1:23:17.700)
for that particular word.
Richard Karp (1:23:22.500)
Yeah, so that's the...
Lex Fridman (1:23:26.380)
It's very different than other algorithms of its kind
Richard Karp (1:23:31.060)
that we're trying to do search, string matching.
Lex Fridman (1:23:35.540)
Yeah, which usually are combinatorial
Lex Fridman (1:23:38.060)
and don't involve the idea of taking a random fingerprint.
Lex Fridman (1:23:42.620)
Yes.
Lex Fridman (1:23:43.580)
And doing the fingerprinting has two advantages.
Lex Fridman (1:23:48.020)
One is that as we slide along the long word,
Richard Karp (1:23:51.580)
digit by digit, we keep a window of a certain size,
Lex Fridman (1:23:57.460)
the size of the word we're looking for,
Lex Fridman (1:24:00.660)
and we compute the fingerprint
Lex Fridman (1:24:03.380)
of every stretch of that length.
Lex Fridman (1:24:07.620)
And it turns out that just a couple of arithmetic operations
Lex Fridman (1:24:11.260)
will take you from the fingerprint of one part
Richard Karp (1:24:15.300)
to what you get when you slide over by one position.
Lex Fridman (1:24:19.860)
So the computation of all the fingerprints is simple.
Lex Fridman (1:24:26.740)
And secondly, it's unlikely if the prime is chosen randomly
Lex Fridman (1:24:32.780)
from a certain range that you will get two of the segments
Richard Karp (1:24:37.500)
in question having the same fingerprint.
Lex Fridman (1:24:39.980)
Right.
Lex Fridman (1:24:41.660)
And so there's a small probability of error
Lex Fridman (1:24:43.940)
which can be checked after the fact,
Lex Fridman (1:24:46.460)
and also the ease of doing the computation
Lex Fridman (1:24:48.700)
because you're working with these fingerprints
Richard Karp (1:24:51.580)
which are remainder's modulo some big prime.
Lex Fridman (1:24:55.620)
So that's the magical thing about randomized algorithms
Richard Karp (1:24:58.020)
is that if you add a little bit of randomness,
Lex Fridman (1:25:02.420)
it somehow allows you to take a pretty naive approach,
Richard Karp (1:25:05.380)
a simple looking approach, and allow it to run extremely well.
Lex Fridman (1:25:10.660)
So can you maybe take a step back and say
Lex Fridman (1:25:14.340)
what is a randomized algorithm, this category of algorithms?
Lex Fridman (1:25:18.300)
Well, it's just the ability to draw a random number
Richard Karp (1:25:22.460)
from such, from some range
Lex Fridman (1:25:27.580)
or to associate a random number with some object
Richard Karp (1:25:32.260)
or to draw that random from some set.
Lex Fridman (1:25:35.220)
So another example is very simple
Richard Karp (1:25:41.940)
if we're conducting a presidential election
Lex Fridman (1:25:46.420)
and we would like to pick the winner.
Richard Karp (1:25:52.300)
In principle, we could draw a random sample
Lex Fridman (1:25:57.300)
of all of the voters in the country.
Lex Fridman (1:25:59.300)
And if it was of substantial size, say a few thousand,
Lex Fridman (1:26:05.700)
then the most popular candidate in that group
Richard Karp (1:26:08.940)
would be very likely to be the correct choice
Lex Fridman (1:26:12.280)
that would come out of counting all the millions of votes.
Lex Fridman (1:26:15.820)
And of course we can't do this because first of all,
Lex Fridman (1:26:18.460)
everybody has to feel that his or her vote counted.
Lex Fridman (1:26:21.900)
And secondly, we can't really do a purely random sample
Lex Fridman (1:26:25.300)
from that population.
Lex Fridman (1:26:28.000)
And I guess thirdly, there could be a tie
Lex Fridman (1:26:30.060)
in which case we wouldn't have a significant difference
Richard Karp (1:26:34.100)
between two candidates.
Lex Fridman (1:26:36.380)
But those things aside,
Richard Karp (1:26:37.580)
if you didn't have all that messiness of human beings,
Lex Fridman (1:26:40.500)
you could prove that that kind of random picking
Richard Karp (1:26:43.100)
would come up again.
Lex Fridman (1:26:43.940)
You just said random picking would solve the problem
Richard Karp (1:26:48.020)
with a very low probability of error.
Lex Fridman (1:26:51.380)
Another example is testing whether a number is prime.
Lex Fridman (1:26:55.540)
So if I wanna test whether 17 is prime,
Lex Fridman (1:27:01.760)
I could pick any number between one and 17,
Richard Karp (1:27:08.460)
raise it to the 16th power modulo 17,
Lex Fridman (1:27:12.340)
and you should get back the original number.
Richard Karp (1:27:15.060)
That's a famous formula due to Fermat about,
Lex Fridman (1:27:19.620)
it's called Fermat's Little Theorem,
Richard Karp (1:27:21.240)
that if you take any number a in the range
Lex Fridman (1:27:29.340)
zero through n minus one,
Lex Fridman (1:27:32.060)
and raise it to the n minus 1th power modulo n,
Lex Fridman (1:27:38.260)
you'll get back the number a if a is prime.
Lex Fridman (1:27:43.860)
So if you don't get back the number a,
Lex Fridman (1:27:45.900)
that's a proof that a number is not prime.
Lex Fridman (1:27:48.300)
And you can show that suitably defined
Lex Fridman (1:27:57.420)
the probability that you will get a value unequaled,
Richard Karp (1:28:09.300)
you will get a violation of Fermat's result is very high.
Lex Fridman (1:28:14.300)
And so this gives you a way of rapidly proving
Richard Karp (1:28:18.580)
that a number is not prime.
Lex Fridman (1:28:21.020)
It's a little more complicated than that
Richard Karp (1:28:22.800)
because there are certain values of n
Lex Fridman (1:28:26.300)
where something a little more elaborate has to be done,
Lex Fridman (1:28:28.600)
but that's the basic idea.
Lex Fridman (1:28:32.580)
Taking an identity that holds for primes,
Lex Fridman (1:28:34.900)
and therefore, if it ever fails on any instance
Lex Fridman (1:28:39.460)
for a non prime, you know that the number is not prime.
Richard Karp (1:28:43.460)
It's a quick choice, a fast choice,
Lex Fridman (1:28:45.660)
fast proof that a number is not prime.
Lex Fridman (1:28:48.740)
Can you maybe elaborate a little bit more
Lex Fridman (1:28:50.940)
what's your intuition why randomness works so well
Lex Fridman (1:28:54.200)
and results in such simple algorithms?
Lex Fridman (1:28:57.500)
Well, the example of conducting an election
Richard Karp (1:29:00.860)
where you could take, in theory, you could take a sample
Lex Fridman (1:29:04.340)
and depend on the validity of the sample
Richard Karp (1:29:07.060)
to really represent the whole
Lex Fridman (1:29:09.180)
is just the basic fact of statistics,
Richard Karp (1:29:12.040)
which gives a lot of opportunities.
Lex Fridman (1:29:17.780)
And I actually exploited that sort of random sampling idea
Richard Karp (1:29:23.180)
in designing an algorithm
Lex Fridman (1:29:25.780)
for counting the number of solutions
Richard Karp (1:29:30.100)
that satisfy a particular formula
Lex Fridman (1:29:33.820)
and propositional logic.
Lex Fridman (1:29:37.640)
A particular, so some version of the satisfiability problem?
Lex Fridman (1:29:44.380)
A version of the satisfiability problem.
Richard Karp (1:29:47.780)
Is there some interesting insight
Lex Fridman (1:29:49.420)
that you wanna elaborate on,
Richard Karp (1:29:50.460)
like what some aspect of that algorithm
Lex Fridman (1:29:53.300)
that might be useful to describe?
Lex Fridman (1:29:57.500)
So you have a collection of formulas
Lex Fridman (1:30:02.500)
and you want to count the number of solutions
Richard Karp (1:30:14.400)
that satisfy at least one of the formulas.
Lex Fridman (1:30:20.440)
And you can count the number of solutions
Richard Karp (1:30:23.500)
that satisfy any particular one of the formulas,
Lex Fridman (1:30:27.360)
but you have to account for the fact
Richard Karp (1:30:29.960)
that that solution might be counted many times
Lex Fridman (1:30:33.720)
if it solves more than one of the formulas.
Lex Fridman (1:30:40.880)
And so what you do is you sample from the formulas
Lex Fridman (1:30:46.880)
according to the number of solutions
Richard Karp (1:30:49.480)
that satisfy each individual one.
Lex Fridman (1:30:53.220)
In that way, you draw a random solution,
Lex Fridman (1:30:55.680)
but then you correct by looking at
Lex Fridman (1:30:59.040)
the number of formulas that satisfy that random solution
Lex Fridman (1:31:04.480)
and don't double count.
Lex Fridman (1:31:08.880)
So you can think of it this way.
Lex Fridman (1:31:11.640)
So you have a matrix of zeros and ones
Lex Fridman (1:31:16.040)
and you wanna know how many columns of that matrix
Richard Karp (1:31:18.980)
contain at least one one.
Lex Fridman (1:31:22.400)
And you can count in each row how many ones there are.
Lex Fridman (1:31:26.040)
So what you can do is draw from the rows
Lex Fridman (1:31:29.440)
according to the number of ones.
Richard Karp (1:31:31.700)
If a row has more ones, it gets drawn more frequently.
Lex Fridman (1:31:35.980)
But then if you draw from that row,
Richard Karp (1:31:39.880)
you have to go up the column
Lex Fridman (1:31:41.480)
and looking at where that same one is repeated
Richard Karp (1:31:44.620)
in different rows and only count it as a success or a hit
Lex Fridman (1:31:51.240)
if it's the earliest row that contains the one.
Lex Fridman (1:31:54.380)
And that gives you a robust statistical estimate
Lex Fridman (1:32:00.300)
of the total number of columns
Richard Karp (1:32:02.020)
that contain at least one of the ones.
Lex Fridman (1:32:04.540)
So that is an example of the same principle
Richard Karp (1:32:09.020)
that was used in studying random sampling.
Lex Fridman (1:32:13.380)
Another viewpoint is that if you have a phenomenon
Richard Karp (1:32:18.940)
that occurs almost all the time,
Lex Fridman (1:32:21.400)
then if you sample one of the occasions where it occurs,
Richard Karp (1:32:28.780)
you're most likely to,
Lex Fridman (1:32:30.640)
and you're looking for an occurrence,
Richard Karp (1:32:32.640)
a random occurrence is likely to work.
Lex Fridman (1:32:34.880)
So that comes up in solving identities,
Richard Karp (1:32:39.480)
solving algebraic identities.
Lex Fridman (1:32:42.680)
You get two formulas that may look very different.
Richard Karp (1:32:46.480)
You wanna know if they're really identical.
Lex Fridman (1:32:49.000)
What you can do is just pick a random value
Lex Fridman (1:32:52.920)
and evaluate the formulas at that value
Lex Fridman (1:32:56.040)
and see if they agree.
Lex Fridman (1:32:58.840)
And you depend on the fact
Lex Fridman (1:33:02.000)
that if the formulas are distinct,
Richard Karp (1:33:04.360)
then they're gonna disagree a lot.
Lex Fridman (1:33:06.840)
And so therefore, a random choice
Richard Karp (1:33:08.480)
will exhibit the disagreement.
Lex Fridman (1:33:12.760)
If there are many ways for the two to disagree
Lex Fridman (1:33:16.560)
and you only need to find one disagreement,
Lex Fridman (1:33:18.560)
then random choice is likely to yield it.
Lex Fridman (1:33:22.600)
And in general, so we've just talked
Lex Fridman (1:33:24.560)
about randomized algorithms,
Lex Fridman (1:33:26.000)
but we can look at the probabilistic analysis of algorithms.
Lex Fridman (1:33:29.680)
And that gives us an opportunity to step back
Lex Fridman (1:33:32.040)
and as you said, everything we've been talking about
Lex Fridman (1:33:35.600)
is worst case analysis.
Richard Karp (1:33:38.000)
Could you maybe comment on the usefulness
Lex Fridman (1:33:43.480)
and the power of worst case analysis
Lex Fridman (1:33:45.400)
versus best case analysis, average case, probabilistic?
Lex Fridman (1:33:51.160)
How do we think about the future
Richard Karp (1:33:52.760)
of theoretical computer science, computer science
Lex Fridman (1:33:56.600)
in the kind of analysis we do of algorithms?
Richard Karp (1:33:59.080)
Does worst case analysis still have a place,
Lex Fridman (1:34:01.600)
an important place?
Richard Karp (1:34:02.760)
Or do we want to try to move forward
Lex Fridman (1:34:04.600)
towards kind of average case analysis?
Lex Fridman (1:34:07.240)
And what are the challenges there?
Lex Fridman (1:34:09.320)
So if worst case analysis shows
Richard Karp (1:34:11.560)
that an algorithm is always good,
Lex Fridman (1:34:15.280)
that's fine.
Richard Karp (1:34:17.240)
If worst case analysis is used to show that the problem,
Lex Fridman (1:34:25.520)
that the solution is not always good,
Richard Karp (1:34:29.000)
then you have to step back and do something else
Lex Fridman (1:34:32.120)
to ask how often will you get a good solution?
Richard Karp (1:34:36.280)
Just to pause on that for a second,
Lex Fridman (1:34:38.040)
that's so beautifully put
Richard Karp (1:34:40.160)
because I think we tend to judge algorithms.
Lex Fridman (1:34:43.280)
We throw them in the trash
Richard Karp (1:34:45.440)
the moment their worst case is shown to be bad.
Lex Fridman (1:34:48.240)
Right, and that's unfortunate.
Richard Karp (1:34:50.680)
I think a good example is going back
Lex Fridman (1:34:56.880)
to the satisfiability problem.
Richard Karp (1:35:00.120)
There are very powerful programs called SAT solvers
Lex Fridman (1:35:04.480)
which in practice fairly reliably solve instances
Richard Karp (1:35:09.920)
with many millions of variables
Lex Fridman (1:35:11.760)
that arise in digital design
Richard Karp (1:35:14.200)
or in proving programs correct in other applications.
Lex Fridman (1:35:20.200)
And so in many application areas,
Richard Karp (1:35:24.480)
even though satisfiability as we've already discussed
Lex Fridman (1:35:27.760)
is NP complete, the SAT solvers will work so well
Richard Karp (1:35:34.840)
that the people in that discipline
Lex Fridman (1:35:37.240)
tend to think of satisfiability as an easy problem.
Lex Fridman (1:35:40.040)
So in other words, just for some reason
Lex Fridman (1:35:45.160)
that we don't entirely understand,
Richard Karp (1:35:47.640)
the instances that people formulate
Lex Fridman (1:35:50.480)
in designing digital circuits or other applications
Richard Karp (1:35:54.320)
are such that satisfiability is not hard to check
Lex Fridman (1:36:04.440)
and even searching for a satisfying solution
Richard Karp (1:36:07.320)
can be done efficiently in practice.
Lex Fridman (1:36:11.520)
And there are many examples.
Richard Karp (1:36:13.200)
For example, we talked about the traveling salesman problem.
Lex Fridman (1:36:18.160)
So just to refresh our memories,
Richard Karp (1:36:21.320)
the problem is you've got a set of cities,
Lex Fridman (1:36:23.440)
you have pairwise distances between cities
Lex Fridman (1:36:28.560)
and you want to find a tour through all the cities
Lex Fridman (1:36:31.320)
that minimizes the total cost of all the edges traversed,
Richard Karp (1:36:36.320)
all the trips between cities.
Lex Fridman (1:36:38.800)
The problem is NP hard,
Lex Fridman (1:36:41.840)
but people using integer programming codes
Lex Fridman (1:36:46.960)
together with some other mathematical tricks
Richard Karp (1:36:51.400)
can solve geometric instances of the problem
Lex Fridman (1:36:57.080)
where the cities are, let's say points in the plane
Lex Fridman (1:37:01.000)
and get optimal solutions to problems
Lex Fridman (1:37:03.120)
with tens of thousands of cities.
Richard Karp (1:37:05.120)
Actually, it'll take a few computer months
Lex Fridman (1:37:08.240)
to solve a problem of that size,
Lex Fridman (1:37:10.280)
but for problems of size a thousand or two,
Lex Fridman (1:37:13.200)
it'll rapidly get optimal solutions,
Richard Karp (1:37:16.320)
provably optimal solutions,
Lex Fridman (1:37:19.000)
even though again, we know that it's unlikely
Richard Karp (1:37:23.000)
that the traveling salesman problem
Lex Fridman (1:37:25.760)
can be solved in polynomial time.
Richard Karp (1:37:28.440)
Are there methodologies like rigorous systematic methodologies
Lex Fridman (1:37:33.440)
for, you said in practice.
Richard Karp (1:37:38.320)
In practice, this algorithm's pretty good.
Lex Fridman (1:37:40.040)
Are there systematic ways of saying
Lex Fridman (1:37:42.160)
in practice, this algorithm's pretty good?
Lex Fridman (1:37:43.800)
So in other words, average case analysis.
Richard Karp (1:37:46.080)
Or you've also mentioned that average case
Lex Fridman (1:37:49.060)
kind of requires you to understand what the typical case is,
Richard Karp (1:37:52.680)
typical instances, and that might be really difficult.
Lex Fridman (1:37:55.480)
That's very difficult.
Lex Fridman (1:37:56.580)
So after I did my original work
Lex Fridman (1:37:59.720)
on showing all these problems through NP complete,
Richard Karp (1:38:06.600)
I looked around for a way to shed some positive light
Lex Fridman (1:38:11.160)
on combinatorial algorithms.
Lex Fridman (1:38:13.800)
And what I tried to do was to study problems,
Lex Fridman (1:38:19.640)
behavior on the average or with high probability.
Lex Fridman (1:38:24.600)
But I had to make some assumptions
Lex Fridman (1:38:26.160)
about what's the probability space?
Lex Fridman (1:38:29.720)
What's the sample space?
Lex Fridman (1:38:30.860)
What do we mean by typical problems?
Richard Karp (1:38:33.860)
That's very hard to say.
Lex Fridman (1:38:35.280)
So I took the easy way out
Lex Fridman (1:38:37.680)
and made some very simplistic assumptions.
Lex Fridman (1:38:40.500)
So I assumed, for example,
Richard Karp (1:38:42.000)
that if we were generating a graph
Lex Fridman (1:38:44.420)
with a certain number of vertices and edges,
Richard Karp (1:38:47.440)
then we would generate the graph
Lex Fridman (1:38:48.920)
by simply choosing one edge at a time at random
Richard Karp (1:38:53.840)
until we got the right number of edges.
Lex Fridman (1:38:56.840)
That's a particular model of random graphs
Richard Karp (1:38:59.800)
that has been studied mathematically a lot.
Lex Fridman (1:39:02.900)
And within that model,
Richard Karp (1:39:05.120)
I could prove all kinds of wonderful things,
Lex Fridman (1:39:07.560)
I and others who also worked on this.
Lex Fridman (1:39:10.640)
So we could show that we know exactly
Lex Fridman (1:39:15.120)
how many edges there have to be
Richard Karp (1:39:16.760)
in order for there be a so called Hamiltonian circuit.
Lex Fridman (1:39:24.040)
That's a cycle that visits each vertex exactly once.
Richard Karp (1:39:31.560)
We know that if the number of edges
Lex Fridman (1:39:35.240)
is a little bit more than n log n,
Richard Karp (1:39:37.520)
where n is the number of vertices,
Lex Fridman (1:39:39.160)
then such a cycle is very likely to exist.
Lex Fridman (1:39:44.000)
And we can give a heuristic
Lex Fridman (1:39:45.680)
that will find it with high probability.
Lex Fridman (1:39:48.880)
And the community in which I was working
Lex Fridman (1:39:54.880)
got a lot of results along these lines.
Lex Fridman (1:39:58.520)
But the field tended to be rather lukewarm
Lex Fridman (1:40:04.080)
about accepting these results as meaningful
Richard Karp (1:40:07.340)
because we were making such a simplistic assumption
Lex Fridman (1:40:09.880)
about the kinds of graphs that we would be dealing with.
Lex Fridman (1:40:13.960)
So we could show all kinds of wonderful things,
Lex Fridman (1:40:16.000)
it was a great playground, I enjoyed doing it.
Lex Fridman (1:40:18.880)
But after a while, I concluded that
Lex Fridman (1:40:27.240)
it didn't have a lot of bite
Richard Karp (1:40:29.040)
in terms of the practical application.
Lex Fridman (1:40:31.640)
Oh the, okay, so there's too much
Richard Karp (1:40:33.480)
into the world of toy problems.
Lex Fridman (1:40:35.280)
Yeah.
Richard Karp (1:40:36.120)
That can, okay.
Lex Fridman (1:40:36.960)
But all right, is there a way to find
Richard Karp (1:40:41.640)
nice representative real world impactful instances
Lex Fridman (1:40:45.120)
of a problem on which demonstrate that an algorithm is good?
Lex Fridman (1:40:48.840)
So this is kind of like the machine learning world,
Lex Fridman (1:40:51.360)
that's kind of what they at his best tries to do
Richard Karp (1:40:54.200)
is find a data set from like the real world
Lex Fridman (1:40:57.920)
and show the performance, all the conferences
Richard Karp (1:41:02.040)
are all focused on beating the performance
Lex Fridman (1:41:04.480)
of on that real world data set.
Lex Fridman (1:41:07.160)
Is there an equivalent in complexity analysis?
Lex Fridman (1:41:11.680)
Not really, Don Knuth started to collect examples
Richard Karp (1:41:19.520)
of graphs coming from various places.
Lex Fridman (1:41:21.640)
So he would have a whole zoo of different graphs
Richard Karp (1:41:26.160)
that he could choose from and he could study
Lex Fridman (1:41:28.480)
the performance of algorithms on different types of graphs.
Lex Fridman (1:41:31.640)
But there it's really important and compelling
Lex Fridman (1:41:37.320)
to be able to define a class of graphs.
Richard Karp (1:41:41.320)
The actual act of defining a class of graphs
Lex Fridman (1:41:44.080)
that you're interested in, it seems to be
Richard Karp (1:41:46.600)
a non trivial step if we're talking about instances
Lex Fridman (1:41:49.480)
that we should care about in the real world.
Richard Karp (1:41:51.560)
Yeah, there's nothing available there
Lex Fridman (1:41:55.880)
that would be analogous to the training set
Richard Karp (1:41:58.800)
for supervised learning where you sort of assume
Lex Fridman (1:42:02.360)
that the world has given you a bunch
Richard Karp (1:42:05.520)
of examples to work with.
Lex Fridman (1:42:10.200)
We don't really have that for problems,
Richard Karp (1:42:14.560)
for combinatorial problems on graphs and networks.
Lex Fridman (1:42:18.200)
You know, there's been a huge growth,
Richard Karp (1:42:21.000)
a big growth of data sets available.
Lex Fridman (1:42:23.960)
Do you think some aspect of theoretical computer science
Richard Karp (1:42:28.200)
might be contradicting my own question while saying it,
Lex Fridman (1:42:30.640)
but will there be some aspect,
Richard Karp (1:42:33.400)
an empirical aspect of theoretical computer science
Lex Fridman (1:42:36.920)
which will allow the fact that these data sets are huge,
Richard Karp (1:42:41.080)
we'll start using them for analysis.
Lex Fridman (1:42:44.080)
Sort of, you know, if you want to say something
Richard Karp (1:42:46.920)
about a graph algorithm, you might take
Lex Fridman (1:42:50.720)
a social network like Facebook and looking at subgraphs
Richard Karp (1:42:55.160)
of that and prove something about the Facebook graph
Lex Fridman (1:42:58.560)
and be respected, and at the same time,
Richard Karp (1:43:01.120)
be respected in the theoretical computer science community.
Lex Fridman (1:43:03.840)
That hasn't been achieved yet, I'm afraid.
Lex Fridman (1:43:06.240)
Is that P equals NP, is that impossible?
Lex Fridman (1:43:10.960)
Is it impossible to publish a successful paper
Richard Karp (1:43:14.560)
in the theoretical computer science community
Lex Fridman (1:43:17.080)
that shows some performance on a real world data set?
Lex Fridman (1:43:22.080)
Or is that really just those are two different worlds?
Lex Fridman (1:43:25.320)
They haven't really come together.
Richard Karp (1:43:27.160)
I would say that there is a field
Lex Fridman (1:43:31.160)
of experimental algorithmics where people,
Richard Karp (1:43:34.640)
sometimes they're given some family of examples.
Lex Fridman (1:43:39.320)
Sometimes they just generate them at random
Lex Fridman (1:43:41.960)
and they report on performance,
Lex Fridman (1:43:45.920)
but there's no convincing evidence
Richard Karp (1:43:50.920)
that the sample is representative of anything at all.
Lex Fridman (1:43:57.600)
So let me ask, in terms of breakthroughs
Lex Fridman (1:44:00.760)
and open problems, what are the most compelling
Lex Fridman (1:44:04.200)
open problems to you and what possible breakthroughs
Lex Fridman (1:44:07.000)
do you see in the near term
Lex Fridman (1:44:08.280)
in terms of theoretical computer science?
Richard Karp (1:44:13.720)
Well, there are all kinds of relationships
Lex Fridman (1:44:15.480)
among complexity classes that can be studied,
Richard Karp (1:44:18.920)
just to mention one thing, I wrote a paper
Lex Fridman (1:44:22.960)
with Richard Lipton in 1979,
Richard Karp (1:44:28.600)
where we asked the following question.
Lex Fridman (1:44:34.520)
If you take a combinatorial problem in NP, let's say,
Lex Fridman (1:44:39.520)
and you choose, and you pick the size of the problem,
Lex Fridman (1:44:49.520)
say it's a traveling salesman problem, but of size 52,
Lex Fridman (1:44:55.720)
and you ask, could you get an efficient,
Lex Fridman (1:45:00.240)
a small Boolean circuit tailored for that size, 52,
Richard Karp (1:45:05.240)
where you could feed the edges of the graph
Lex Fridman (1:45:08.240)
in as Boolean inputs and get, as an output,
Richard Karp (1:45:12.240)
the question of whether or not
Lex Fridman (1:45:13.560)
there's a tour of a certain length.
Lex Fridman (1:45:16.760)
And that would, in other words, briefly,
Lex Fridman (1:45:19.600)
what you would say in that case
Richard Karp (1:45:21.480)
is that the problem has small circuits,
Lex Fridman (1:45:24.240)
polynomial size circuits.
Richard Karp (1:45:28.200)
Now, we know that if P is equal to NP,
Lex Fridman (1:45:31.280)
then, in fact, these problems will have small circuits,
Lex Fridman (1:45:35.800)
but what about the converse?
Lex Fridman (1:45:37.400)
Could a problem have small circuits,
Richard Karp (1:45:39.240)
meaning that an algorithm tailored to any particular size
Lex Fridman (1:45:43.440)
could work well, and yet not be a polynomial time algorithm?
Richard Karp (1:45:48.440)
That is, you couldn't write it as a single,
Lex Fridman (1:45:50.120)
uniform algorithm, good for all sizes.
Richard Karp (1:45:52.960)
Just to clarify, small circuits
Lex Fridman (1:45:55.800)
for a problem of particular size,
Richard Karp (1:45:57.720)
by small circuits for a problem of particular size,
Lex Fridman (1:46:02.200)
or even further constraint,
Richard Karp (1:46:04.000)
small circuit for a particular...
Lex Fridman (1:46:07.480)
No, for all the inputs of that size.
Lex Fridman (1:46:10.160)
Is that a trivial problem for a particular instance?
Lex Fridman (1:46:13.680)
So, coming up, an automated way
Richard Karp (1:46:15.640)
of coming up with a circuit.
Lex Fridman (1:46:17.960)
I guess that's just an answer.
Richard Karp (1:46:19.200)
That would be hard, yeah.
Lex Fridman (1:46:22.040)
But there's the existential question.
Richard Karp (1:46:25.400)
Everybody talks nowadays about existential questions.
Lex Fridman (1:46:29.000)
Existential challenges.
Richard Karp (1:46:35.640)
You could ask the question,
Lex Fridman (1:46:38.880)
does the Hamiltonian circuit problem
Richard Karp (1:46:43.960)
have a small circuit for every size,
Lex Fridman (1:46:49.440)
for each size, a different small circuit?
Richard Karp (1:46:51.800)
In other words, could you tailor solutions
Lex Fridman (1:46:55.600)
depending on the size, and get polynomial size?
Richard Karp (1:47:00.560)
Even if P is not equal to NP.
Lex Fridman (1:47:02.640)
Right.
Richard Karp (1:47:06.680)
That would be fascinating if that's true.
Lex Fridman (1:47:08.600)
Yeah, what we proved is that if that were possible,
Richard Karp (1:47:14.760)
then something strange would happen in complexity theory.
Lex Fridman (1:47:18.840)
Some high level class which I could briefly describe,
Richard Karp (1:47:26.800)
something strange would happen.
Lex Fridman (1:47:28.360)
So, I'll take a stab at describing what I mean.
Richard Karp (1:47:31.960)
Sure, let's go there.
Lex Fridman (1:47:33.880)
So, we have to define this hierarchy
Richard Karp (1:47:37.640)
in which the first level of the hierarchy is P,
Lex Fridman (1:47:41.440)
and the second level is NP.
Lex Fridman (1:47:44.080)
And what is NP?
Lex Fridman (1:47:45.240)
NP involves statements of the form
Richard Karp (1:47:48.200)
there exists a something such that something holds.
Lex Fridman (1:47:53.720)
So, for example, there exists the coloring
Richard Karp (1:47:59.960)
such that a graph can be colored
Lex Fridman (1:48:01.880)
with only that number of colors.
Richard Karp (1:48:06.640)
Or there exists a Hamiltonian circuit.
Lex Fridman (1:48:09.120)
There's a statement about this graph.
Richard Karp (1:48:10.800)
Yeah, so the NP deals with statements of that kind,
Lex Fridman (1:48:22.840)
that there exists a solution.
Richard Karp (1:48:26.200)
Now, you could imagine a more complicated expression
Lex Fridman (1:48:32.600)
which says for all x there exists a y
Richard Karp (1:48:38.600)
such that some proposition holds involving both x and y.
Lex Fridman (1:48:47.200)
So, that would say, for example, in game theory,
Richard Karp (1:48:50.040)
for all strategies for the first player,
Lex Fridman (1:48:54.920)
there exists a strategy for the second player
Richard Karp (1:48:57.720)
such that the first player wins.
Lex Fridman (1:48:59.520)
That would be at the second level of the hierarchy.
Richard Karp (1:49:03.360)
The third level would be there exists an A
Lex Fridman (1:49:06.000)
such that for all B there exists a C,
Richard Karp (1:49:08.400)
that something holds.
Lex Fridman (1:49:09.240)
And you could imagine going higher and higher
Richard Karp (1:49:11.200)
in the hierarchy.
Lex Fridman (1:49:12.680)
And you'd expect that the complexity classes
Richard Karp (1:49:17.480)
that correspond to those different cases
Lex Fridman (1:49:22.400)
would get bigger and bigger.
Lex Fridman (1:49:27.080)
What do you mean by bigger and bigger?
Lex Fridman (1:49:28.240)
Sorry, sorry.
Richard Karp (1:49:29.520)
They'd get harder and harder to solve.
Lex Fridman (1:49:30.720)
Harder and harder, right.
Richard Karp (1:49:32.360)
Harder and harder to solve.
Lex Fridman (1:49:35.360)
And what Lipton and I showed was
Richard Karp (1:49:37.720)
that if NP had small circuits,
Lex Fridman (1:49:41.560)
then this hierarchy would collapse down
Richard Karp (1:49:44.160)
to the second level.
Lex Fridman (1:49:46.200)
In other words, you wouldn't get any more mileage
Richard Karp (1:49:48.400)
by complicating your expressions with three quantifiers
Lex Fridman (1:49:51.520)
or four quantifiers or any number.
Richard Karp (1:49:55.400)
I'm not sure what to make of that exactly.
Lex Fridman (1:49:57.720)
Well, I think it would be evidence
Richard Karp (1:49:59.280)
that NP doesn't have small circuits
Lex Fridman (1:50:02.920)
because something so bizarre would happen.
Lex Fridman (1:50:07.080)
But again, it's only evidence, not proof.
Lex Fridman (1:50:09.000)
Well, yeah, that's not even evidence
Richard Karp (1:50:12.520)
because you're saying P is not equal to NP
Lex Fridman (1:50:16.960)
because something bizarre has to happen.
Richard Karp (1:50:19.560)
I mean, that's proof by the lack of bizarreness
Lex Fridman (1:50:25.120)
in our science.
Lex Fridman (1:50:26.600)
But it seems like just the very notion
Lex Fridman (1:50:31.400)
of P equals NP would be bizarre.
Lex Fridman (1:50:33.040)
So any way you arrive at, there's no way.
Lex Fridman (1:50:36.240)
You have to fight the dragon at some point.
Richard Karp (1:50:38.440)
Yeah, okay.
Lex Fridman (1:50:39.280)
Well, anyway, for whatever it's worth,
Richard Karp (1:50:41.880)
that's what we proved.
Lex Fridman (1:50:43.320)
Awesome.
Lex Fridman (1:50:45.720)
So that's a potential space of interesting problems.
Lex Fridman (1:50:49.400)
Yeah.
Richard Karp (1:50:50.240)
Let me ask you about this other world
Lex Fridman (1:50:54.120)
that of machine learning, of deep learning.
Richard Karp (1:50:57.280)
What's your thoughts on the history
Lex Fridman (1:50:59.640)
and the current progress of machine learning field
Richard Karp (1:51:02.600)
that's often progressed sort of separately
Lex Fridman (1:51:05.760)
as a space of ideas and space of people
Richard Karp (1:51:08.840)
than the theoretical computer science
Lex Fridman (1:51:10.920)
or just even computer science world?
Richard Karp (1:51:12.640)
Yeah, it's really very different
Lex Fridman (1:51:15.680)
from the theoretical computer science world
Richard Karp (1:51:17.800)
because the results about it,
Lex Fridman (1:51:22.280)
algorithmic performance tend to be empirical.
Richard Karp (1:51:25.400)
It's more akin to the world of SAT solvers
Lex Fridman (1:51:28.880)
where we observe that for formulas arising in practice,
Richard Karp (1:51:33.880)
the solver does well.
Lex Fridman (1:51:35.920)
So it's of that type.
Richard Karp (1:51:38.520)
We're moving into the empirical evaluation of algorithms.
Lex Fridman (1:51:45.280)
Now, it's clear that there've been huge successes
Richard Karp (1:51:47.800)
in image processing, robotics,
Lex Fridman (1:51:52.720)
natural language processing, a little less so,
Lex Fridman (1:51:55.400)
but across the spectrum of game playing is another one.
Lex Fridman (1:52:00.400)
There've been great successes and one of those effects
Richard Karp (1:52:07.320)
is that it's not too hard to become a millionaire
Lex Fridman (1:52:10.040)
if you can get a reputation in machine learning
Lex Fridman (1:52:12.360)
and there'll be all kinds of companies
Lex Fridman (1:52:13.960)
that will be willing to offer you the moon
Richard Karp (1:52:16.360)
because they think that if they have AI at their disposal,
Lex Fridman (1:52:23.360)
then they can solve all kinds of problems.
Lex Fridman (1:52:25.560)
But there are limitations.
Lex Fridman (1:52:30.040)
One is that the solutions that you get
Richard Karp (1:52:38.000)
to supervise learning problems
Lex Fridman (1:52:44.800)
through convolutional neural networks
Richard Karp (1:52:50.000)
seem to perform amazingly well
Lex Fridman (1:52:55.120)
even for inputs that are outside the training set.
Lex Fridman (1:53:03.120)
But we don't have any theoretical understanding
Lex Fridman (1:53:06.240)
of why that's true.
Richard Karp (1:53:09.360)
Secondly, the solutions, the networks that you get
Lex Fridman (1:53:14.560)
are very hard to understand
Lex Fridman (1:53:16.560)
and so very little insight comes out.
Lex Fridman (1:53:19.960)
So yeah, yeah, they may seem to work on your training set
Lex Fridman (1:53:23.960)
and you may be able to discover whether your photos occur
Lex Fridman (1:53:28.960)
in a different sample of inputs or not,
Lex Fridman (1:53:35.720)
but we don't really know what's going on.
Lex Fridman (1:53:37.520)
We don't know the features that distinguish the photographs
Richard Karp (1:53:41.680)
or the objects are not easy to characterize.
Lex Fridman (1:53:49.560)
Well, it's interesting because you mentioned
Richard Karp (1:53:51.160)
coming up with a small circuit to solve
Lex Fridman (1:53:54.280)
a particular size problem.
Richard Karp (1:53:56.360)
It seems that neural networks are kind of small circuits.
Lex Fridman (1:53:59.880)
In a way, yeah.
Lex Fridman (1:54:01.360)
But they're not programs.
Lex Fridman (1:54:02.800)
Sort of like the things you've designed
Richard Karp (1:54:04.960)
are algorithms, programs, algorithms.
Lex Fridman (1:54:08.920)
Neural networks aren't able to develop algorithms
Richard Karp (1:54:12.600)
to solve a problem.
Lex Fridman (1:54:14.480)
Well, they are algorithms.
Richard Karp (1:54:16.920)
It's just that they're...
Lex Fridman (1:54:18.520)
But sort of, yeah, it could be a semantic question,
Lex Fridman (1:54:25.280)
but there's not a algorithmic style manipulation
Lex Fridman (1:54:31.120)
of the input.
Richard Karp (1:54:33.400)
Perhaps you could argue there is.
Lex Fridman (1:54:35.320)
Yeah, well.
Richard Karp (1:54:37.120)
It feels a lot more like a function of the input.
Lex Fridman (1:54:40.520)
Yeah, it's a function.
Richard Karp (1:54:41.720)
It's a computable function.
Lex Fridman (1:54:43.120)
Once you have the network,
Richard Karp (1:54:46.040)
you can simulate it on a given input
Lex Fridman (1:54:49.360)
and figure out the output.
Lex Fridman (1:54:51.320)
But if you're trying to recognize images,
Lex Fridman (1:54:58.720)
then you don't know what features of the image
Richard Karp (1:55:00.880)
are really being determinant of what the circuit is doing.
Lex Fridman (1:55:09.440)
The circuit is sort of very intricate
Lex Fridman (1:55:14.040)
and it's not clear that the simple characteristics
Lex Fridman (1:55:21.000)
that you're looking for,
Richard Karp (1:55:22.040)
the edges of the objects or whatever they may be,
Lex Fridman (1:55:26.120)
they're not emerging from the structure of the circuit.
Richard Karp (1:55:29.600)
Well, it's not clear to us humans,
Lex Fridman (1:55:31.120)
but it's clear to the circuit.
Richard Karp (1:55:33.040)
Yeah, well, right.
Lex Fridman (1:55:34.880)
I mean, it's not clear to sort of the elephant
Lex Fridman (1:55:39.880)
how the human brain works,
Lex Fridman (1:55:44.600)
but it's clear to us humans,
Richard Karp (1:55:46.880)
we can explain to each other our reasoning
Lex Fridman (1:55:49.160)
and that's why the cognitive science
Lex Fridman (1:55:50.760)
and psychology field exists.
Lex Fridman (1:55:52.720)
Maybe the whole thing of being explainable to humans
Richard Karp (1:55:56.280)
is a little bit overrated.
Lex Fridman (1:55:57.720)
Oh, maybe, yeah.
Richard Karp (1:55:59.760)
I guess you can say the same thing about our brain
Lex Fridman (1:56:02.480)
that when we perform acts of cognition,
Richard Karp (1:56:06.160)
we have no idea how we do it really.
Lex Fridman (1:56:08.760)
We do though, I mean, at least for the visual system,
Richard Karp (1:56:13.680)
the auditory system and so on,
Lex Fridman (1:56:15.200)
we do get some understanding of the principles
Richard Karp (1:56:19.240)
that they operate under,
Lex Fridman (1:56:20.200)
but for many deeper cognitive tasks, we don't have that.
Richard Karp (1:56:25.600)
That's right.
Lex Fridman (1:56:26.640)
Let me ask, you've also been doing work on bioinformatics.
Lex Fridman (1:56:33.000)
Does it amaze you that the fundamental building blocks?
Lex Fridman (1:56:36.960)
So if we take a step back and look at us humans,
Richard Karp (1:56:39.840)
the building blocks used by evolution
Lex Fridman (1:56:41.800)
to build us intelligent human beings
Richard Karp (1:56:44.640)
is all contained there in our DNA.
Lex Fridman (1:56:48.320)
It's amazing and what's really amazing
Richard Karp (1:56:51.880)
is that we are beginning to learn how to edit DNA,
Lex Fridman (1:57:00.920)
which is very, very, very fascinating.
Richard Karp (1:57:05.560)
This ability to take a sequence,
Lex Fridman (1:57:15.240)
find it in the genome and do something to it.
Richard Karp (1:57:18.960)
I mean, that's really taking our biological systems
Lex Fridman (1:57:21.320)
towards the world of algorithms.
Richard Karp (1:57:24.480)
Yeah, but it raises a lot of questions.
Lex Fridman (1:57:30.000)
You have to distinguish between doing it on an individual
Richard Karp (1:57:33.920)
or doing it on somebody's germline,
Lex Fridman (1:57:35.760)
which means that all of their descendants will be affected.
Lex Fridman (1:57:40.280)
So that's like an ethical.
Lex Fridman (1:57:42.200)
Yeah, so it raises very severe ethical questions.
Lex Fridman (1:57:50.520)
And even doing it on individuals,
Lex Fridman (1:57:56.800)
there's a lot of hubris involved
Richard Karp (1:57:59.480)
that you can assume that knocking out a particular gene
Lex Fridman (1:58:04.160)
is gonna be beneficial
Richard Karp (1:58:05.400)
because you don't know what the side effects
Lex Fridman (1:58:07.000)
are going to be.
Lex Fridman (1:58:08.960)
So we have this wonderful new world of gene editing,
Lex Fridman (1:58:20.200)
which is very, very impressive
Lex Fridman (1:58:23.200)
and it could be used in agriculture,
Lex Fridman (1:58:27.280)
it could be used in medicine in various ways.
Lex Fridman (1:58:32.680)
But very serious ethical problems arise.
Lex Fridman (1:58:37.240)
What are to you the most interesting places
Richard Karp (1:58:39.880)
where algorithms, sort of the ethical side
Lex Fridman (1:58:44.560)
is an exceptionally challenging thing
Richard Karp (1:58:46.040)
that I think we're going to have to tackle
Lex Fridman (1:58:48.040)
with all of genetic engineering.
Lex Fridman (1:58:51.840)
But on the algorithmic side,
Lex Fridman (1:58:53.760)
there's a lot of benefit that's possible.
Lex Fridman (1:58:55.520)
So is there areas where you see exciting possibilities
Lex Fridman (1:59:00.280)
for algorithms to help model, optimize,
Lex Fridman (1:59:03.360)
study biological systems?
Lex Fridman (1:59:06.720)
Yeah, I mean, we can certainly analyze genomic data
Richard Karp (1:59:12.480)
to figure out which genes are operative in the cell
Lex Fridman (1:59:17.440)
and under what conditions
Lex Fridman (1:59:18.800)
and which proteins affect one another,
Lex Fridman (1:59:21.280)
which proteins physically interact.
Richard Karp (1:59:27.400)
We can sequence proteins and modify them.
Lex Fridman (1:59:32.680)
Is there some aspect of that
Richard Karp (1:59:33.840)
that's a computer science problem
Lex Fridman (1:59:35.920)
or is that still fundamentally a biology problem?
Richard Karp (1:59:39.840)
Well, it's a big data,
Lex Fridman (1:59:41.600)
it's a statistical big data problem for sure.
Lex Fridman (1:59:45.720)
So the biological data sets are increasing,
Lex Fridman (1:59:49.280)
our ability to study our ancestry,
Richard Karp (1:59:55.680)
to study the tendencies towards disease,
Lex Fridman (1:59:59.960)
to personalize treatment according to what's in our genomes
Richard Karp (20:03.400)
this mental arithmetic.
Lex Fridman (20:06.640)
Yeah, there's something to that.
Richard Karp (20:10.160)
Some of the most popular videos on the internet
Lex Fridman (20:13.920)
is there's a YouTube channel called Numberphile
Richard Karp (20:18.000)
that shows off different mathematical ideas.
Lex Fridman (20:20.440)
I see.
Richard Karp (20:21.280)
There's still something really profoundly interesting
Lex Fridman (20:23.360)
to people about math, the beauty of it.
Richard Karp (20:27.160)
Something, even if they don't understand
Lex Fridman (20:31.240)
the basic concept even being discussed,
Richard Karp (20:33.640)
there's something compelling to it.
Lex Fridman (20:35.040)
What do you think that is?
Richard Karp (20:37.160)
Any lessons you drew from your early teen years
Lex Fridman (20:40.520)
when you were showing off to your friends with the numbers?
Richard Karp (20:45.360)
Like what is it that attracts us
Lex Fridman (20:47.640)
to the beauty of mathematics do you think?
Richard Karp (20:51.340)
The general population, not just the computer scientists
Lex Fridman (20:54.560)
and mathematicians.
Richard Karp (20:56.560)
I think that you can do amazing things.
Lex Fridman (20:59.600)
You can test whether large numbers are prime.
Richard Karp (21:04.440)
You can solve little puzzles
Lex Fridman (21:09.560)
about cannibals and missionaries.
Lex Fridman (21:13.360)
And that's a kind of achievement, it's puzzle solving.
Lex Fridman (21:19.280)
And at a higher level, the fact that you can do
Richard Karp (21:22.720)
this reasoning that you can prove
Lex Fridman (21:24.600)
in an absolutely ironclad way that some of the angles
Richard Karp (21:28.960)
of a triangle is 180 degrees.
Lex Fridman (21:32.600)
Yeah, it's a nice escape from the messiness
Richard Karp (21:35.300)
of the real world where nothing can be proved.
Lex Fridman (21:38.080)
So, and we'll talk about it, but sometimes the ability
Richard Karp (21:41.320)
to map the real world into such problems
Lex Fridman (21:43.520)
where you can't prove it is a powerful step.
Richard Karp (21:47.080)
Yeah.
Lex Fridman (21:47.900)
It's amazing that we can do it.
Richard Karp (21:48.740)
Of course, another attribute of geeks
Lex Fridman (21:50.040)
is they're not necessarily endowed
Richard Karp (21:53.620)
with emotional intelligence, so they can live
Lex Fridman (21:57.220)
in a world of abstractions without having
Richard Karp (21:59.960)
to master the complexities of dealing with people.
Lex Fridman (22:06.620)
So just to link on the historical note,
Richard Karp (22:09.440)
as a PhD student in 1955, you joined the computational lab
Lex Fridman (22:13.200)
at Harvard where Howard Aiken had built the Mark I
Lex Fridman (22:17.040)
and the Mark IV computers.
Lex Fridman (22:19.760)
Just to take a step back into that history,
Lex Fridman (22:22.000)
what were those computers like?
Lex Fridman (22:26.360)
The Mark IV filled a large room,
Richard Karp (22:31.160)
much bigger than this large office
Lex Fridman (22:33.700)
that we were talking in now.
Lex Fridman (22:36.880)
And you could walk around inside it.
Lex Fridman (22:39.120)
There were rows of relays.
Richard Karp (22:43.340)
You could just walk around the interior
Lex Fridman (22:45.360)
and the machine would sometimes fail because of bugs,
Richard Karp (22:53.140)
which literally meant flying creatures
Lex Fridman (22:56.220)
landing on the switches.
Lex Fridman (22:59.820)
So I never used that machine for any practical purpose.
Lex Fridman (23:06.260)
The lab eventually acquired one of the earlier
Richard Karp (23:12.680)
commercial computers.
Lex Fridman (23:14.600)
And this was already in the 60s?
Richard Karp (23:16.680)
No, in the mid 50s, or late 50s.
Lex Fridman (23:19.840)
There was already commercial computers in the...
Richard Karp (23:21.800)
Yeah, we had a Univac, a Univac with 2,000 words of storage.
Lex Fridman (23:27.280)
And so you had to work hard to allocate the memory properly
Richard Karp (23:31.720)
to also the excess time from one word to another
Lex Fridman (23:36.120)
depended on the number of the particular words.
Lex Fridman (23:41.120)
And so there was an art to sort of arranging
Lex Fridman (23:44.880)
the storage allocation to make fetching data rapid.
Richard Karp (23:51.240)
Were you attracted to this actual physical world
Lex Fridman (23:54.960)
implementation of mathematics?
Lex Fridman (23:58.140)
So it's a mathematical machine that's actually doing
Lex Fridman (24:01.400)
the math physically?
Richard Karp (24:03.120)
No, not at all.
Lex Fridman (24:04.800)
I think I was attracted to the underlying algorithms.
Lex Fridman (24:09.400)
But did you draw any inspiration?
Lex Fridman (24:12.880)
So could you have imagined, like what did you imagine
Lex Fridman (24:17.240)
was the future of these giant computers?
Lex Fridman (24:20.120)
Could you have imagined that 60 years later
Lex Fridman (24:22.000)
we'd have billions of these computers all over the world?
Lex Fridman (24:25.780)
I couldn't imagine that, but there was a sense
Richard Karp (24:30.560)
in the laboratory that this was the wave of the future.
Lex Fridman (24:36.120)
In fact, my mother influenced me.
Richard Karp (24:38.920)
She told me that data processing was gonna be really big
Lex Fridman (24:42.320)
and I should get into it.
Richard Karp (24:43.920)
You're a smart woman.
Lex Fridman (24:47.280)
Yeah, she was a smart woman.
Lex Fridman (24:49.080)
And there was just a feeling that this was going
Lex Fridman (24:53.080)
to change the world, but I didn't think of it
Richard Karp (24:55.680)
in terms of personal computing.
Lex Fridman (24:57.200)
I had no anticipation that we would be walking around
Richard Karp (25:02.920)
with computers in our pockets or anything like that.
Lex Fridman (25:06.120)
Did you see computers as tools, as mathematical mechanisms
Richard Karp (25:12.800)
to analyze sort of the theoretical computer science,
Lex Fridman (25:16.540)
or as the AI folks, which is an entire other community
Richard Karp (25:21.000)
of dreamers, as something that could one day
Lex Fridman (25:24.480)
have human level intelligence?
Richard Karp (25:26.840)
Well, AI wasn't very much on my radar.
Lex Fridman (25:29.560)
I did read Turing's paper about the...
Richard Karp (25:33.200)
The Turing Test, Computing and Intelligence.
Lex Fridman (25:38.080)
Yeah, the Turing test.
Lex Fridman (25:40.520)
What'd you think about that paper?
Lex Fridman (25:41.840)
Was that just like science fiction?
Richard Karp (25:45.600)
I thought that it wasn't a very good test
Lex Fridman (25:48.280)
because it was too subjective.
Lex Fridman (25:50.440)
So I didn't feel that the Turing test
Lex Fridman (25:55.280)
was really the right way to calibrate
Lex Fridman (25:58.400)
how intelligent an algorithm could be.
Lex Fridman (26:01.000)
But to linger on that, do you think it's,
Richard Karp (26:03.240)
because you've come up with some incredible tests later on,
Lex Fridman (26:07.800)
tests on algorithms, right, that are like strong,
Richard Karp (26:12.200)
reliable, robust across a bunch of different classes
Lex Fridman (26:15.320)
of algorithms, but returning to this emotional mess
Richard Karp (26:20.020)
that is intelligence, do you think it's possible
Lex Fridman (26:22.840)
to come up with a test that's as ironclad
Lex Fridman (26:26.420)
as some of the computational complexity work?
Lex Fridman (26:31.320)
Well, I think the greater question
Richard Karp (26:32.800)
is whether it's possible to achieve human level intelligence.
Lex Fridman (26:38.720)
Right, so first of all, let me, at the philosophical level,
Lex Fridman (26:42.080)
do you think it's possible to create algorithms
Lex Fridman (26:46.320)
that reason and would seem to us
Lex Fridman (26:51.320)
to have the same kind of intelligence as human beings?
Lex Fridman (26:54.080)
It's an open question.
Richard Karp (26:58.160)
It seems to me that most of the achievements
Lex Fridman (27:04.080)
have operate within a very limited set of ground rules
Lex Fridman (27:11.840)
and for a very limited, precise task,
Lex Fridman (27:15.400)
which is a quite different situation
Richard Karp (27:17.600)
from the processes that go on in the minds of humans,
Lex Fridman (27:22.340)
which where they have to sort of function
Richard Karp (27:25.040)
in changing environments, they have emotions,
Lex Fridman (27:30.120)
they have physical attributes for exploring
Richard Karp (27:37.920)
their environment, they have intuition,
Lex Fridman (27:41.400)
they have desires, emotions, and I don't see anything
Richard Karp (27:46.400)
in the current achievements of what's called AI
Lex Fridman (27:54.440)
that come close to that capability.
Richard Karp (27:56.940)
I don't think there's any computer program
Lex Fridman (28:02.160)
which surpasses a six month old child
Richard Karp (28:05.720)
in terms of comprehension of the world.
Lex Fridman (28:10.680)
Do you think this complexity of human intelligence,
Richard Karp (28:15.560)
all the cognitive abilities we have,
Lex Fridman (28:17.080)
all the emotion, do you think that could be reduced one day
Richard Karp (28:21.380)
or just fundamentally can it be reduced
Lex Fridman (28:23.960)
to a set of algorithms or an algorithm?
Lex Fridman (28:27.260)
So can a Turing machine achieve human level intelligence?
Lex Fridman (28:33.180)
I am doubtful about that.
Richard Karp (28:35.940)
I guess the argument in favor of it
Lex Fridman (28:38.640)
is that the human brain seems to achieve what we call
Richard Karp (28:47.240)
intelligence cognitive abilities of different kinds.
Lex Fridman (28:51.820)
And if you buy the premise that the human brain
Richard Karp (28:54.300)
is just an enormous interconnected set of switches,
Lex Fridman (28:58.600)
so to speak, then in principle, you should be able
Richard Karp (29:03.120)
to diagnose what that interconnection structure is like,
Lex Fridman (29:07.420)
characterize the individual switches,
Lex Fridman (29:09.400)
and build a simulation outside.
Lex Fridman (29:14.100)
But while that may be true in principle,
Richard Karp (29:17.640)
that cannot be the way we're eventually
Lex Fridman (29:19.900)
gonna tackle this problem.
Richard Karp (29:25.960)
That does not seem like a feasible way to go about it.
Lex Fridman (29:29.360)
So there is, however, an existence proof that
Richard Karp (29:32.480)
if you believe that the brain is just a network of neurons
Lex Fridman (29:42.440)
operating by rules, I guess you could say
Richard Karp (29:45.240)
that that's an existence proof of the capabilities
Lex Fridman (29:50.160)
of a mechanism, but it would be almost impossible
Richard Karp (29:55.100)
to acquire the information unless we got enough insight
Lex Fridman (2:00:06.960)
and what tendencies for disease we have,
Richard Karp (2:00:10.440)
to be able to predict what troubles might come upon us
Lex Fridman (2:00:13.960)
in the future and anticipate them,
Richard Karp (2:00:16.120)
to understand whether you,
Lex Fridman (2:00:24.360)
for a woman, whether her proclivity for breast cancer
Richard Karp (2:00:31.560)
is so strong enough that she would want
Lex Fridman (2:00:33.680)
to take action to avoid it.
Richard Karp (2:00:37.680)
You dedicate your 1985 Turing Award lecture
Lex Fridman (2:00:41.040)
to the memory of your father.
Lex Fridman (2:00:42.600)
What's your fondest memory of your dad?
Lex Fridman (2:00:53.040)
Seeing him standing in front of a class at the blackboard,
Richard Karp (2:00:57.880)
drawing perfect circles by hand
Lex Fridman (2:01:03.960)
and showing his ability to attract the interest
Richard Karp (2:01:08.960)
of the motley collection of eighth grade students
Lex Fridman (2:01:14.760)
that he was teaching.
Richard Karp (2:01:19.120)
When did you get a chance to see him
Lex Fridman (2:01:21.640)
draw the perfect circles?
Richard Karp (2:01:24.280)
On rare occasions, I would get a chance
Lex Fridman (2:01:27.480)
to sneak into his classroom and observe him.
Lex Fridman (2:01:33.160)
And I think he was at his best in the classroom.
Lex Fridman (2:01:36.320)
I think he really came to life and had fun,
Richard Karp (2:01:42.720)
not only teaching, but engaging in chit chat
Lex Fridman (2:01:49.080)
with the students and ingratiating himself
Richard Karp (2:01:52.280)
with the students.
Lex Fridman (2:01:53.800)
And what I inherited from that is the great desire
Richard Karp (2:02:00.040)
to be a teacher.
Lex Fridman (2:02:01.920)
I retired recently and a lot of my former students came,
Richard Karp (2:02:08.320)
students with whom I had done research
Lex Fridman (2:02:11.200)
or who had read my papers or who had been in my classes.
Lex Fridman (2:02:15.680)
And when they talked about me,
Lex Fridman (2:02:22.520)
they talked not about my 1979 paper or 1992 paper,
Lex Fridman (2:02:27.520)
but about what came away in my classes.
Lex Fridman (2:02:33.600)
And not just the details, but just the approach
Lex Fridman (2:02:36.400)
and the manner of teaching.
Lex Fridman (2:02:40.240)
And so I sort of take pride in the,
Richard Karp (2:02:43.600)
at least in my early years as a faculty member at Berkeley,
Lex Fridman (2:02:47.680)
I was exemplary in preparing my lectures
Lex Fridman (2:02:51.760)
and I always came in prepared to the teeth,
Lex Fridman (2:02:56.760)
and able therefore to deviate according
Richard Karp (2:02:59.320)
to what happened in the class,
Lex Fridman (2:03:01.200)
and to really provide a model for the students.
Lex Fridman (2:03:08.760)
So is there advice you can give out for others
Lex Fridman (2:03:14.640)
on how to be a good teacher?
Lex Fridman (2:03:16.520)
So preparation is one thing you've mentioned,
Lex Fridman (2:03:19.000)
being exceptionally well prepared,
Lex Fridman (2:03:20.440)
but there are other things,
Lex Fridman (2:03:21.520)
pieces of advice that you can impart?
Richard Karp (2:03:24.480)
Well, the top three would be preparation, preparation,
Lex Fridman (2:03:27.400)
and preparation.
Lex Fridman (2:03:29.760)
Why is preparation so important, I guess?
Lex Fridman (2:03:32.840)
It's because it gives you the ease
Richard Karp (2:03:34.440)
to deal with any situation that comes up in the classroom.
Lex Fridman (2:03:38.680)
And if you discover that you're not getting through one way,
Richard Karp (2:03:44.520)
you can do it another way.
Lex Fridman (2:03:45.880)
If the students have questions,
Richard Karp (2:03:47.320)
you can handle the questions.
Lex Fridman (2:03:49.000)
Ultimately, you're also feeling the crowd,
Richard Karp (2:03:54.000)
the students of what they're struggling with,
Lex Fridman (2:03:57.080)
what they're picking up,
Richard Karp (2:03:57.920)
just looking at them through the questions,
Lex Fridman (2:03:59.720)
but even just through their eyes.
Richard Karp (2:04:01.440)
Yeah, that's right.
Lex Fridman (2:04:02.280)
And because of the preparation, you can dance.
Richard Karp (2:04:05.400)
You can dance, you can say it another way,
Lex Fridman (2:04:09.800)
or give it another angle.
Richard Karp (2:04:11.640)
Are there, in particular, ideas and algorithms
Lex Fridman (2:04:14.840)
of computer science that you find
Richard Karp (2:04:17.080)
were big aha moments for students,
Lex Fridman (2:04:19.920)
where they, for some reason, once they got it,
Richard Karp (2:04:22.760)
it clicked for them and they fell in love
Lex Fridman (2:04:24.720)
with computer science?
Lex Fridman (2:04:26.640)
Or is it individual, is it different for everybody?
Lex Fridman (2:04:29.320)
It's different for everybody.
Richard Karp (2:04:30.840)
You have to work differently with students.
Lex Fridman (2:04:32.720)
Some of them just don't need much influence.
Richard Karp (2:04:40.120)
They're just running with what they're doing
Lex Fridman (2:04:42.360)
and they just need an ear now and then.
Richard Karp (2:04:44.800)
Others need a little prodding.
Lex Fridman (2:04:47.200)
Others need to be persuaded to collaborate among themselves
Richard Karp (2:04:50.880)
rather than working alone.
Lex Fridman (2:04:53.000)
They have their personal ups and downs,
Lex Fridman (2:04:57.200)
so you have to deal with each student as a human being
Lex Fridman (2:05:03.000)
and bring out the best.
Richard Karp (2:05:06.640)
Humans are complicated.
Lex Fridman (2:05:08.160)
Yeah.
Richard Karp (2:05:09.240)
Perhaps a silly question.
Lex Fridman (2:05:11.240)
If you could relive a moment in your life outside of family
Richard Karp (2:05:15.400)
because it made you truly happy,
Lex Fridman (2:05:17.440)
or perhaps because it changed the direction of your life
Lex Fridman (2:05:19.920)
in a profound way, what moment would you pick?
Lex Fridman (2:05:24.560)
I was kind of a lazy student as an undergraduate,
Lex Fridman (2:05:28.240)
and even in my first year in graduate school.
Lex Fridman (2:05:33.320)
And I think it was when I started doing research,
Richard Karp (2:05:37.280)
I had a couple of summer jobs where I was able to contribute
Lex Fridman (2:05:41.520)
and I had an idea.
Lex Fridman (2:05:45.040)
And then there was one particular course
Lex Fridman (2:05:47.760)
on mathematical methods and operations research
Richard Karp (2:05:51.520)
where I just gobbled up the material
Lex Fridman (2:05:53.600)
and I scored 20 points higher than anybody else in the class
Richard Karp (2:05:57.560)
then came to the attention of the faculty.
Lex Fridman (2:06:00.680)
And it made me realize that I had some ability
Richard Karp (2:06:04.600)
that I was going somewhere.
Lex Fridman (2:06:09.160)
You realize you're pretty good at this thing.
Richard Karp (2:06:12.360)
I don't think there's a better way to end it, Richard.
Lex Fridman (2:06:14.320)
It was a huge honor.
Richard Karp (2:06:15.240)
Thank you for decades of incredible work.
Lex Fridman (2:06:18.240)
Thank you for talking to me.
Richard Karp (2:06:19.080)
Thank you, it's been a great pleasure.
Lex Fridman (2:06:21.080)
You're a superb interviewer.
Richard Karp (2:06:23.920)
I'll stop it.
Lex Fridman (2:06:26.760)
Thanks for listening to this conversation with Richard Karp.
Lex Fridman (2:06:29.640)
And thank you to our sponsors, 8sleep and Cash App.
Lex Fridman (2:06:34.120)
Please consider supporting this podcast
Richard Karp (2:06:35.880)
by going to 8sleep.com slash Lex
Lex Fridman (2:06:39.160)
to check out their awesome mattress
Lex Fridman (2:06:41.920)
and downloading Cash App and using code LexPodcast.
Lex Fridman (2:06:46.040)
Click the links, buy the stuff,
Richard Karp (2:06:48.320)
even just visiting the site
Lex Fridman (2:06:49.800)
but also considering the purchase.
Richard Karp (2:06:51.600)
Helps them know that this podcast
Lex Fridman (2:06:54.200)
is worth supporting in the future.
Richard Karp (2:06:55.840)
It really is the best way to support this journey I'm on.
Lex Fridman (2:06:59.680)
If you enjoy this thing, subscribe on YouTube,
Richard Karp (2:07:02.040)
review it with Five Stars and Apple Podcast,
Lex Fridman (2:07:04.120)
support it on Patreon, connect with me on Twitter
Richard Karp (2:07:07.360)
at Lex Friedman if you can figure out how to spell that.
Lex Fridman (2:07:11.360)
And now let me leave you with some words from Isaac Asimov.
Richard Karp (2:07:16.000)
I do not fear computers.
Lex Fridman (2:07:18.160)
I fear lack of them.
Richard Karp (2:07:19.800)
Thank you for listening and hope to see you next time.
Lex Fridman (30:00.100)
into the operation of the brain.
Lex Fridman (30:02.780)
But there's so much mystery there.
Lex Fridman (30:04.300)
Do you think, what do you make of consciousness,
Richard Karp (30:06.700)
for example, as an example of something
Lex Fridman (30:11.020)
we completely have no clue about?
Richard Karp (30:13.180)
The fact that we have this subjective experience.
Lex Fridman (30:15.940)
Is it possible that this network of,
Richard Karp (30:19.780)
this circuit of switches is able to create
Lex Fridman (30:22.900)
something like consciousness?
Richard Karp (30:24.940)
To know its own identity.
Lex Fridman (30:26.820)
Yeah, to know the algorithm, to know itself.
Richard Karp (30:30.260)
To know itself.
Lex Fridman (30:32.100)
I think if you try to define that rigorously,
Richard Karp (30:35.340)
you'd have a lot of trouble.
Lex Fridman (30:36.660)
Yeah, that seems to be.
Lex Fridman (30:39.380)
So I know that there are many who believe
Lex Fridman (30:47.040)
that general intelligence can be achieved,
Lex Fridman (30:52.620)
and there are even some who feel certain
Lex Fridman (30:55.780)
that the singularity will come
Lex Fridman (30:59.180)
and we will be surpassed by the machines
Lex Fridman (31:01.740)
which will then learn more and more about themselves
Lex Fridman (31:04.380)
and reduce humans to an inferior breed.
Lex Fridman (31:08.640)
I am doubtful that this will ever be achieved.
Richard Karp (31:12.700)
Just for the fun of it, could you linger on why,
Lex Fridman (31:17.020)
what's your intuition, why you're doubtful?
Lex Fridman (31:19.100)
So there are quite a few people that are extremely worried
Lex Fridman (31:23.060)
about this existential threat of artificial intelligence,
Richard Karp (31:26.380)
of us being left behind
Lex Fridman (31:29.220)
by this super intelligent new species.
Lex Fridman (31:32.340)
What's your intuition why that's not quite likely?
Lex Fridman (31:37.860)
Just because none of the achievements in speech
Richard Karp (31:43.480)
or robotics or natural language processing
Lex Fridman (31:48.580)
or creation of flexible computer assistants
Richard Karp (31:52.660)
or any of that comes anywhere near close
Lex Fridman (31:56.460)
to that level of cognition.
Lex Fridman (32:00.300)
What do you think about ideas of sort of,
Lex Fridman (32:02.260)
if we look at Moore's Law and exponential improvement
Lex Fridman (32:06.140)
to allow us, that would surprise us?
Lex Fridman (32:09.300)
Sort of our intuition fall apart
Richard Karp (32:11.540)
with exponential improvement because, I mean,
Lex Fridman (32:14.660)
we're not able to kind of,
Richard Karp (32:16.060)
we kind of think in linear improvement.
Lex Fridman (32:18.260)
We're not able to imagine a world
Richard Karp (32:20.220)
that goes from the Mark I computer to an iPhone X.
Lex Fridman (32:26.180)
Yeah.
Lex Fridman (32:27.540)
So do you think we could be really surprised
Lex Fridman (32:31.260)
by the exponential growth?
Richard Karp (32:33.420)
Or on the flip side, is it possible
Lex Fridman (32:37.540)
that also intelligence is actually way, way, way, way harder,
Lex Fridman (32:42.220)
even with exponential improvement to be able to crack?
Lex Fridman (32:47.100)
I don't think any constant factor improvement
Richard Karp (32:50.300)
could change things.
Lex Fridman (32:53.980)
I mean, given our current comprehension
Richard Karp (32:58.100)
of what cognition requires,
Lex Fridman (33:04.940)
it seems to me that multiplying the speed of the switches
Richard Karp (33:08.760)
by a factor of a thousand or a million
Lex Fridman (33:13.580)
will not be useful until we really understand
Richard Karp (33:16.600)
the organizational principle behind the network of switches.
Lex Fridman (33:23.140)
Well, let's jump into the network of switches
Lex Fridman (33:25.420)
and talk about combinatorial algorithms if we could.
Lex Fridman (33:29.860)
Let's step back with the very basics.
Lex Fridman (33:31.700)
What are combinatorial algorithms?
Lex Fridman (33:33.700)
And what are some major examples
Lex Fridman (33:35.080)
of problems they aim to solve?
Lex Fridman (33:38.140)
A combinatorial algorithm is one which deals
Richard Karp (33:43.140)
with a system of discrete objects
Lex Fridman (33:48.340)
that can occupy various states
Richard Karp (33:52.300)
or take on various values from a discrete set of values
Lex Fridman (33:59.700)
and need to be arranged or selected
Richard Karp (34:06.620)
in such a way as to achieve some,
Lex Fridman (34:10.520)
to minimize some cost function.
Richard Karp (34:13.100)
Or to prove the existence
Lex Fridman (34:16.220)
of some combinatorial configuration.
Lex Fridman (34:19.980)
So an example would be coloring the vertices of a graph.
Lex Fridman (34:25.020)
What's a graph?
Richard Karp (34:27.280)
Let's step back.
Lex Fridman (34:28.120)
So it's fun to ask one of the greatest
Richard Karp (34:34.780)
computer scientists of all time
Lex Fridman (34:36.180)
the most basic questions in the beginning of most books.
Lex Fridman (34:39.260)
But for people who might not know,
Lex Fridman (34:41.420)
but in general how you think about it, what is a graph?
Richard Karp (34:44.480)
A graph, that's simple.
Lex Fridman (34:47.260)
It's a set of points, certain pairs of which
Richard Karp (34:51.220)
are joined by lines called edges.
Lex Fridman (34:55.060)
And they sort of represent the,
Richard Karp (34:58.740)
in different applications represent the interconnections
Lex Fridman (35:02.340)
between discrete objects.
Lex Fridman (35:05.900)
So they could be the interactions,
Lex Fridman (35:07.740)
interconnections between switches in a digital circuit
Richard Karp (35:12.500)
or interconnections indicating the communication patterns
Lex Fridman (35:16.380)
of a human community.
Lex Fridman (35:19.300)
And they could be directed or undirected
Lex Fridman (35:21.420)
and then as you've mentioned before, might have costs.
Richard Karp (35:25.540)
Right, they can be directed or undirected.
Lex Fridman (35:27.700)
They can be, you can think of them as,
Richard Karp (35:30.660)
if you think, if a graph were representing
Lex Fridman (35:34.260)
a communication network, then the edge could be undirected
Richard Karp (35:38.700)
meaning that information could flow along it
Lex Fridman (35:41.780)
in both directions or it could be directed
Richard Karp (35:44.540)
with only one way communication.
Lex Fridman (35:46.980)
A road system is another example of a graph
Richard Karp (35:49.740)
with weights on the edges.
Lex Fridman (35:52.220)
And then a lot of problems of optimizing the efficiency
Richard Karp (35:57.220)
of such networks or learning about the performance
Lex Fridman (36:04.660)
of such networks are the object of combinatorial algorithms.
Lex Fridman (36:11.340)
So it could be scheduling classes at a school
Lex Fridman (36:15.620)
where the vertices, the nodes of the network
Richard Karp (36:20.620)
are the individual classes and the edges indicate
Lex Fridman (36:25.620)
the constraints which say that certain classes
Richard Karp (36:28.580)
cannot take place at the same time
Lex Fridman (36:30.860)
or certain teachers are available only for certain classes,
Richard Karp (36:34.980)
et cetera.
Lex Fridman (36:36.300)
Or I talked earlier about the assignment problem
Richard Karp (36:41.300)
of matching the boys with the girls
Lex Fridman (36:43.060)
where you have there a graph with an edge
Richard Karp (36:48.060)
from each boy to each girl with a weight
Lex Fridman (36:51.300)
indicating the cost.
Richard Karp (36:53.460)
Or in logical design of computers,
Lex Fridman (36:58.460)
you might want to find a set of so called gates,
Richard Karp (37:04.300)
switches that perform logical functions
Lex Fridman (37:07.500)
which can be interconnected to each other
Lex Fridman (37:10.060)
and perform logical functions which can be interconnected
Lex Fridman (37:13.740)
to realize some function.
Lex Fridman (37:15.580)
So you might ask how many gates do you need
Lex Fridman (37:22.460)
in order for a circuit to give a yes output
Richard Karp (37:33.220)
if at least a given number of its inputs are ones
Lex Fridman (37:38.220)
and no if fewer are present.
Richard Karp (37:42.980)
My favorite's probably all the work with network flow.
Lex Fridman (37:46.580)
So anytime you have, I don't know why it's so compelling
Lex Fridman (37:50.780)
but there's something just beautiful about it.
Lex Fridman (37:52.420)
It seems like there's so many applications
Lex Fridman (37:54.340)
and communication networks and traffic flow
Lex Fridman (38:00.700)
that you can map into these and then you could think
Richard Karp (38:03.340)
of pipes and water going through pipes
Lex Fridman (38:05.580)
and you could optimize it in different ways.
Richard Karp (38:07.260)
There's something always visually and intellectually
Lex Fridman (38:11.140)
compelling to me about it.
Lex Fridman (38:12.340)
And of course you've done work there.
Lex Fridman (38:15.940)
Yeah, so there the edges represent channels
Richard Karp (38:21.540)
along which some commodity can flow.
Lex Fridman (38:24.540)
It might be gas, it might be water, it might be information.
Richard Karp (38:29.900)
Maybe supply chain as well like products being.
Lex Fridman (38:33.900)
Products flowing from one operation to another.
Lex Fridman (38:37.740)
And the edges have a capacity which is the rate
Lex Fridman (38:41.140)
at which the commodity can flow.
Lex Fridman (38:43.740)
And a central problem is to determine
Lex Fridman (38:49.220)
given a network of these channels.
Richard Karp (38:51.700)
In this case the edges are communication channels.
Lex Fridman (38:56.380)
The challenge is to find the maximum rate
Richard Karp (39:01.380)
at which the information can flow along these channels
Lex Fridman (39:05.460)
to get from a source to a destination.
Lex Fridman (39:09.060)
And that's a fundamental combinatorial problem
Lex Fridman (39:12.620)
that I've worked on jointly with the scientist Jack Edmonds.
Richard Karp (39:19.780)
I think we're the first to give a formal proof
Lex Fridman (39:22.380)
that this maximum flow problem through a network
Richard Karp (39:27.460)
can be solved in polynomial time.
Lex Fridman (39:30.660)
Which I remember the first time I learned that.
Richard Karp (39:33.900)
Just learning that in maybe even grad school.
Lex Fridman (39:39.740)
I don't think it was even undergrad.
Richard Karp (39:41.100)
No, algorithm, yeah.
Lex Fridman (39:43.380)
Do network flows get taught in basic algorithms courses?
Richard Karp (39:50.100)
Yes, probably.
Lex Fridman (39:51.100)
Okay, so yeah, I remember being very surprised
Richard Karp (39:53.740)
that max flow is a polynomial time algorithm.
Lex Fridman (39:56.780)
That there's a nice fast algorithm that solves max flow.
Lex Fridman (39:59.900)
So there is an algorithm named after you in Edmonds.
Lex Fridman (40:06.540)
The Edmond Carp algorithm for max flow.
Lex Fridman (40:08.380)
So what was it like tackling that problem
Lex Fridman (40:12.580)
and trying to arrive at a polynomial time solution?
Lex Fridman (40:15.660)
And maybe you can describe the algorithm.
Lex Fridman (40:17.180)
Maybe you can describe what's the running time complexity
Richard Karp (40:19.900)
that you showed.
Lex Fridman (40:20.740)
Yeah, well, first of all,
Lex Fridman (40:23.340)
what is a polynomial time algorithm?
Lex Fridman (40:25.620)
Perhaps we could discuss that.
Lex Fridman (40:28.580)
So yeah, let's actually just even, yeah.
Lex Fridman (40:31.580)
What is algorithmic complexity?
Lex Fridman (40:34.140)
What are the major classes of algorithm complexity?
Lex Fridman (40:38.220)
So in a problem like the assignment problem
Richard Karp (40:41.860)
or scheduling schools or any of these applications,
Lex Fridman (40:48.820)
you have a set of input data which might, for example,
Richard Karp (40:53.820)
be a set of vertices connected by edges
Lex Fridman (41:01.460)
with you're given for each edge the capacity of the edge.
Lex Fridman (41:07.340)
And you have algorithms which are,
Lex Fridman (41:12.220)
think of them as computer programs with operations
Richard Karp (41:16.700)
such as addition, subtraction, multiplication, division,
Lex Fridman (41:19.940)
comparison of numbers, and so on.
Lex Fridman (41:22.020)
And you're trying to construct an algorithm
Lex Fridman (41:29.540)
based on those operations, which will determine
Richard Karp (41:33.860)
in a minimum number of computational steps
Lex Fridman (41:37.260)
the answer to the problem.
Richard Karp (41:38.460)
In this case, the computational step
Lex Fridman (41:41.100)
is one of those operations.
Lex Fridman (41:43.380)
And the answer to the problem is let's say
Lex Fridman (41:46.060)
the configuration of the network
Richard Karp (41:50.420)
that carries the maximum amount of flow.
Lex Fridman (41:54.860)
And an algorithm is said to run in polynomial time
Richard Karp (41:59.940)
if as a function of the size of the input,
Lex Fridman (42:04.980)
the number of vertices, the number of edges, and so on,
Richard Karp (42:09.180)
the number of basic computational steps grows
Lex Fridman (42:12.460)
only as some fixed power of that size.
Richard Karp (42:15.220)
A linear algorithm would execute a number of steps
Lex Fridman (42:21.940)
linearly proportional to the size.
Richard Karp (42:24.660)
Quadratic algorithm would be steps proportional
Lex Fridman (42:27.700)
to the square of the size, and so on.
Lex Fridman (42:30.660)
And algorithms whose running time is bounded
Lex Fridman (42:34.660)
by some fixed power of the size
Richard Karp (42:37.260)
are called polynomial algorithms.
Lex Fridman (42:39.900)
Yeah.
Lex Fridman (42:40.740)
And that's supposed to be relatively fast class
Lex Fridman (42:44.060)
of algorithms.
Richard Karp (42:44.900)
That's right.
Lex Fridman (42:45.740)
Theoreticians take that to be the definition
Richard Karp (42:49.500)
of an algorithm being efficient.
Lex Fridman (42:54.460)
And we're interested in which problems can be solved
Richard Karp (42:57.940)
by such efficient algorithms.
Lex Fridman (43:02.300)
One can argue whether that's the right definition
Richard Karp (43:04.940)
of efficient because you could have an algorithm
Lex Fridman (43:08.100)
whose running time is the 10,000th power
Richard Karp (43:11.420)
of the size of the input,
Lex Fridman (43:12.540)
and that wouldn't be really efficient.
Lex Fridman (43:15.860)
And in practice, it's oftentimes reducing
Lex Fridman (43:19.220)
from an N squared algorithm to an N log N
Richard Karp (43:22.620)
or a linear time is practically the jump
Lex Fridman (43:26.940)
that you wanna make to allow a real world system
Richard Karp (43:30.260)
to solve a problem.
Lex Fridman (43:31.220)
Yeah, that's also true because especially
Richard Karp (43:33.260)
as we get very large networks,
Lex Fridman (43:35.860)
the size can be in the millions,
Lex Fridman (43:38.060)
and then anything above N log N
Lex Fridman (43:43.700)
where N is the size would be too much
Richard Karp (43:46.940)
for a practical solution.
Lex Fridman (43:49.940)
Okay, so that's polynomial time algorithms.
Lex Fridman (43:52.500)
What other classes of algorithms are there?
Lex Fridman (43:56.140)
What's, so that usually they designate polynomials
Richard Karp (44:01.100)
of the letter P.
Lex Fridman (44:02.380)
Yeah.
Richard Karp (44:03.220)
There's also NP, NP complete and NP hard.
Lex Fridman (44:06.180)
Yeah.
Lex Fridman (44:07.140)
So can you try to disentangle those
Lex Fridman (44:10.900)
by trying to define them simply?
Richard Karp (44:14.260)
Right, so a polynomial time algorithm
Lex Fridman (44:16.940)
is one whose running time is bounded
Richard Karp (44:20.460)
by a polynomial in the size of the input.
Lex Fridman (44:24.540)
Then the class of such algorithms is called P.
Lex Fridman (44:29.380)
In the worst case, by the way, we should say, right?
Lex Fridman (44:31.420)
Yeah.
Lex Fridman (44:32.260)
So for every case of the problem.
Lex Fridman (44:33.100)
Yes, that's right, and that's very important
Richard Karp (44:34.300)
that in this theory, when we measure the complexity
Lex Fridman (44:39.500)
of an algorithm, we really measure the number of steps,
Richard Karp (44:45.020)
the growth of the number of steps in the worst case.
Lex Fridman (44:48.900)
So you may have an algorithm that runs very rapidly
Richard Karp (44:53.460)
in most cases, but if there's any case
Lex Fridman (44:56.820)
where it gets into a very long computation,
Richard Karp (45:00.100)
that would increase the computational complexity
Lex Fridman (45:03.420)
by this measure.
Lex Fridman (45:05.300)
And that's a very important issue
Lex Fridman (45:07.340)
because there are, as we may discuss later,
Richard Karp (45:10.540)
there are some very important algorithms
Lex Fridman (45:13.220)
which don't have a good standing
Richard Karp (45:15.500)
from the point of view of their worst case performance
Lex Fridman (45:18.100)
and yet are very effective.
Lex Fridman (45:20.620)
So theoreticians are interested in P,
Lex Fridman (45:24.300)
the class of problem solvable in polynomial time.
Richard Karp (45:27.500)
Then there's NP, which is the class of problems
Lex Fridman (45:34.500)
which may be hard to solve, but when confronted
Richard Karp (45:42.700)
with a solution, you can check it in polynomial time.
Lex Fridman (45:46.620)
Let me give you an example there.
Lex Fridman (45:49.180)
So if we look at the assignment problem,
Lex Fridman (45:52.420)
so you have N boys, you have N girls,
Richard Karp (45:55.940)
the number of numbers that you need to write down
Lex Fridman (45:58.740)
to specify the problem instance is N squared.
Lex Fridman (46:03.740)
And the question is how many steps are needed to solve it?
Lex Fridman (46:11.540)
And Jack Edmonds and I were the first to show
Richard Karp (46:15.660)
that it could be done in time and cubed.
Lex Fridman (46:20.260)
Earlier algorithms required N to the fourth.
Lex Fridman (46:23.900)
So as a polynomial function of the size of the input,
Lex Fridman (46:27.340)
this is a fast algorithm.
Richard Karp (46:30.180)
Now to illustrate the class NP, the question is
Lex Fridman (46:34.100)
how long would it take to verify
Lex Fridman (46:38.940)
that a solution is optimal?
Lex Fridman (46:42.700)
So for example, if the input was a graph,
Richard Karp (46:48.140)
we might want to find the largest clique in the graph
Lex Fridman (46:53.140)
or a clique is a set of vertices such that any vertex,
Richard Karp (46:58.860)
each vertex in the set is adjacent to each of the others.
Lex Fridman (47:03.980)
So the clique is a complete subgraph.
Richard Karp (47:08.940)
Yeah, so if it's a Facebook social network,
Lex Fridman (47:11.900)
everybody's friends with everybody else, close clique.
Richard Karp (47:15.300)
No, that would be what's called a complete graph.
Lex Fridman (47:17.300)
It would be.
Richard Karp (47:18.220)
No, I mean within that clique.
Lex Fridman (47:20.660)
Within that clique, yeah.
Richard Karp (47:21.900)
Yeah, they're all friends.
Lex Fridman (47:25.580)
So a complete graph is when?
Richard Karp (47:27.820)
Everybody is friendly.
Lex Fridman (47:28.820)
As everybody is friends with everybody, yeah.
Lex Fridman (47:31.340)
So the problem might be to determine whether
Lex Fridman (47:36.340)
in a given graph there exists a clique of a certain size.
Richard Karp (47:43.020)
Now that turns out to be a very hard problem,
Lex Fridman (47:45.740)
but if somebody hands you a clique and asks you to check
Richard Karp (47:50.740)
whether it is, hands you a set of vertices
Lex Fridman (47:55.180)
and asks you to check whether it's a clique,
Richard Karp (47:58.900)
you could do that simply by exhaustively looking
Lex Fridman (48:01.900)
at all of the edges between the vertices and the clique
Lex Fridman (48:05.220)
and verifying that they're all there.
Lex Fridman (48:08.020)
And that's a polynomial time algorithm.
Richard Karp (48:10.540)
That's a polynomial.
Lex Fridman (48:11.540)
So the problem of finding the clique
Richard Karp (48:17.620)
appears to be extremely hard,
Lex Fridman (48:19.300)
but the problem of verifying a clique
Richard Karp (48:22.980)
to see if it reaches a target number of vertices
Lex Fridman (48:28.260)
is easy to verify.
Lex Fridman (48:31.700)
So finding the clique is hard, checking it is easy.
Lex Fridman (48:35.740)
Problems of that nature are called
Richard Karp (48:39.020)
nondeterministic polynomial time algorithms,
Lex Fridman (48:42.460)
and that's the class NP.
Lex Fridman (48:45.700)
And what about NP complete and NP hard?
Lex Fridman (48:48.360)
Okay, let's talk about problems
Richard Karp (48:50.900)
where you're getting a yes or no answer
Lex Fridman (48:53.800)
rather than a numerical value.
Lex Fridman (48:55.460)
So either there is a perfect matching
Lex Fridman (48:58.780)
of the boys with the girls or there isn't.
Richard Karp (49:04.180)
It's clear that every problem in P is also in NP.
Lex Fridman (49:10.580)
If you can solve the problem exactly,
Richard Karp (49:12.580)
then you can certainly verify the solution.
Lex Fridman (49:17.540)
On the other hand, there are problems in the class NP.
Richard Karp (49:23.820)
This is the class of problems that are easy to check,
Lex Fridman (49:27.140)
although they may be hard to solve.
Richard Karp (49:29.700)
It's not at all clear that problems in NP lie in P.
Lex Fridman (49:33.780)
So for example, if we're looking
Richard Karp (49:36.220)
at scheduling classes at a school,
Lex Fridman (49:39.300)
the fact that you can verify when handed a schedule
Richard Karp (49:44.300)
for the school, whether it meets all the requirements,
Lex Fridman (49:47.980)
that doesn't mean that you can find the schedule rapidly.
Lex Fridman (49:51.380)
So intuitively, NP, nondeterministic polynomial checking
Lex Fridman (49:55.780)
rather than finding, is going to be harder than,
Richard Karp (50:03.180)
is going to include, is easier.
Lex Fridman (50:06.140)
Checking is easier, and therefore the class of problems
Richard Karp (50:08.820)
that can be checked appears to be much larger
Lex Fridman (50:11.940)
than the class of problems that can be solved.
Lex Fridman (50:14.620)
And then you keep adding appears to,
Lex Fridman (50:17.380)
and sort of these additional words that designate
Richard Karp (50:22.220)
that we don't know for sure yet.
Lex Fridman (50:24.060)
We don't know for sure.
Lex Fridman (50:25.180)
So the theoretical question, which is considered
Lex Fridman (50:28.140)
to be the most central problem
Richard Karp (50:30.420)
in theoretical computer science,
Lex Fridman (50:32.640)
or at least computational complexity theory,
Richard Karp (50:36.380)
combinatorial algorithm theory,
Lex Fridman (50:38.560)
the question is whether P is equal to NP.
Richard Karp (50:43.600)
If P were equal to NP, it would be amazing.
Lex Fridman (50:46.300)
It would mean that every problem
Richard Karp (50:54.240)
where a solution can be rapidly checked
Lex Fridman (50:58.080)
can actually be solved in polynomial time.
Richard Karp (51:00.900)
We don't really believe that's true.
Lex Fridman (51:03.420)
If you're scheduling classes at a school,
Richard Karp (51:05.780)
we expect that if somebody hands you a satisfying schedule,
Lex Fridman (51:13.020)
you can verify that it works.
Richard Karp (51:15.620)
That doesn't mean that you should be able
Lex Fridman (51:17.140)
to find such a schedule.
Lex Fridman (51:18.940)
So intuitively, NP encompasses a lot more problems than P.
Lex Fridman (51:24.140)
So can we take a small tangent
Lex Fridman (51:28.020)
and break apart that intuition?
Lex Fridman (51:30.460)
So do you, first of all, think that the biggest
Richard Karp (51:34.540)
sort of open problem in computer science,
Lex Fridman (51:36.200)
maybe mathematics, is whether P equals NP?
Lex Fridman (51:40.000)
Do you think P equals NP,
Lex Fridman (51:43.220)
or do you think P is not equal to NP?
Richard Karp (51:46.300)
If you had to bet all your money on it.
Lex Fridman (51:48.820)
I would bet that P is unequal to NP,
Richard Karp (51:52.020)
simply because there are problems
Lex Fridman (51:54.280)
that have been around for centuries
Lex Fridman (51:55.940)
and have been studied intensively in mathematics,
Lex Fridman (51:58.980)
and even more so in the last 50 years
Richard Karp (52:02.060)
since the P versus NP was stated.
Lex Fridman (52:05.600)
And no polynomial time algorithms have been found
Richard Karp (52:10.180)
for these easy to check problems.
Lex Fridman (52:13.700)
So one example is a problem that goes back
Richard Karp (52:17.620)
to the mathematician Gauss,
Lex Fridman (52:19.860)
who was interested in factoring large numbers.
Lex Fridman (52:24.480)
So we know what a number is prime
Lex Fridman (52:27.960)
if it cannot be written as the product
Richard Karp (52:31.500)
of two or more numbers unequal to one.
Lex Fridman (52:36.340)
So if we can factor a number like 91, it's seven times 13.
Lex Fridman (52:43.820)
But if I give you 20 digit or 30 digit numbers,
Lex Fridman (52:50.860)
you're probably gonna be at a loss
Richard Karp (52:52.540)
to have any idea whether they can be factored.
Lex Fridman (52:56.840)
So the problem of factoring very large numbers
Richard Karp (53:00.020)
does not appear to have an efficient solution.
Lex Fridman (53:06.960)
But once you have found the factors,
Richard Karp (53:11.680)
expressed the number as a product of two smaller numbers,
Lex Fridman (53:16.600)
you can quickly verify that they are factors of the number.
Lex Fridman (53:19.960)
And your intuition is a lot of people finding,
Lex Fridman (53:23.540)
a lot of brilliant people have tried to find algorithms
Richard Karp (53:25.720)
for this one particular problem.
Lex Fridman (53:26.960)
There's many others like it that are really well studied
Lex Fridman (53:30.520)
and it would be great to find an efficient algorithm for.
Lex Fridman (53:33.960)
Right, and in fact, we have some results
Richard Karp (53:40.320)
that I was instrumental in obtaining following up on work
Lex Fridman (53:44.680)
by the mathematician Stephen Cook
Richard Karp (53:48.720)
to show that within the class NP of easy to check problems,
Lex Fridman (53:53.720)
easy to check problems, there's a huge number
Richard Karp (53:57.080)
that are equivalent in the sense that either all of them
Lex Fridman (54:00.640)
or none of them lie in P.
Lex Fridman (54:03.200)
And this happens only if P is equal to NP.
Lex Fridman (54:06.400)
So if P is unequal to NP, we would also know
Richard Karp (54:11.240)
that virtually all the standard combinatorial problems,
Lex Fridman (54:16.240)
virtually all the standard combinatorial problems,
Richard Karp (54:20.280)
if P is unequal to NP, none of them can be solved
Lex Fridman (54:23.860)
in polynomial time.
Lex Fridman (54:25.920)
Can you explain how that's possible
Lex Fridman (54:28.560)
to tie together so many problems in a nice bunch
Lex Fridman (54:32.280)
that if one is proven to be efficient, then all are?
Lex Fridman (54:36.560)
The first and most important stage of progress
Richard Karp (54:40.600)
was a result by Stephen Cook who showed that a certain problem
Lex Fridman (54:49.680)
called the satisfiability problem of propositional logic
Richard Karp (54:55.880)
is as hard as any problem in the class P.
Lex Fridman (55:00.200)
So the propositional logic problem is expressed
Richard Karp (55:05.200)
in terms of expressions involving the logical operations
Lex Fridman (55:11.040)
and, or, and not operating on variables
Richard Karp (55:16.860)
that can be either true or false.
Lex Fridman (55:19.240)
So an instance of the problem would be some formula
Richard Karp (55:24.560)
involving and, or, and not.
Lex Fridman (55:28.240)
And the question would be whether there is an assignment
Richard Karp (55:31.180)
of truth values to the variables in the problem
Lex Fridman (55:34.900)
that would make the formula true.
Lex Fridman (55:37.400)
So for example, if I take the formula A or B
Lex Fridman (55:42.920)
and A or not B and not A or B and not A or not B
Lex Fridman (55:49.360)
and take the conjunction of all four
Lex Fridman (55:51.280)
of those so called expressions,
Richard Karp (55:54.600)
you can determine that no assignment of truth values
Lex Fridman (55:59.080)
to the variables A and B will allow that conjunction
Richard Karp (56:03.920)
of what are called clauses to be true.
Lex Fridman (56:09.200)
So that's an example of a formula in propositional logic
Richard Karp (56:16.920)
involving expressions based on the operations and, or, and not.
Lex Fridman (56:23.800)
That's an example of a problem which is not satisfiable.
Richard Karp (56:27.280)
There is no solution that satisfies
Lex Fridman (56:29.280)
all of those constraints.
Richard Karp (56:31.200)
I mean that's like one of the cleanest and fundamental
Lex Fridman (56:33.800)
problems in computer science.
Richard Karp (56:35.320)
It's like a nice statement of a really hard problem.
Lex Fridman (56:37.680)
It's a nice statement of a really hard problem
Lex Fridman (56:39.960)
and what Cook showed is that every problem in NP
Lex Fridman (56:50.120)
can be reexpressed as an instance
Richard Karp (56:53.560)
of the satisfiability problem.
Lex Fridman (56:56.080)
So to do that, he used the observation
Richard Karp (57:02.080)
that a very simple abstract machine
Lex Fridman (57:04.160)
called the Turing machine can be used
Richard Karp (57:08.360)
to describe any algorithm.
Lex Fridman (57:14.960)
An algorithm for any realistic computer
Richard Karp (57:17.800)
can be translated into an equivalent algorithm
Lex Fridman (57:22.840)
on one of these Turing machines
Richard Karp (57:25.840)
which are extremely simple.
Lex Fridman (57:27.960)
So a Turing machine, there's a tape and you can
Richard Karp (57:30.560)
Yeah, you have data on a tape
Lex Fridman (57:33.360)
and you have basic instructions,
Richard Karp (57:35.720)
a finite list of instructions which say,
Lex Fridman (57:39.640)
if you're reading a particular symbol on the tape
Lex Fridman (57:43.520)
and you're in a particular state,
Lex Fridman (57:45.520)
then you can move to a different state
Lex Fridman (57:49.840)
and change the state of the number
Lex Fridman (57:51.400)
or the element that you were looking at,
Richard Karp (57:53.760)
the cell of the tape that you were looking at.
Lex Fridman (57:55.760)
And that was like a metaphor and a mathematical construct
Richard Karp (57:58.560)
that Turing put together
Lex Fridman (57:59.880)
to represent all possible computation.
Richard Karp (58:02.200)
All possible computation.
Lex Fridman (58:03.600)
Now, one of these so called Turing machines
Richard Karp (58:06.240)
is too simple to be useful in practice,
Lex Fridman (58:09.320)
but for theoretical purposes,
Richard Karp (58:11.360)
we can depend on the fact that an algorithm
Lex Fridman (58:15.880)
for any computer can be translated
Richard Karp (58:18.840)
into one that would run on a Turing machine.
Lex Fridman (58:21.320)
And then using that fact,
Richard Karp (58:26.280)
he could sort of describe
Lex Fridman (58:31.240)
any possible non deterministic polynomial time algorithm.
Richard Karp (58:35.640)
Any algorithm for a problem in NP
Lex Fridman (58:40.000)
could be expressed as a sequence of moves
Richard Karp (58:44.520)
of the Turing machine described
Lex Fridman (58:47.360)
in terms of reading a symbol on the tape
Richard Karp (58:54.160)
while you're in a given state
Lex Fridman (58:55.560)
and moving to a new state and leaving behind a new symbol.
Lex Fridman (59:00.000)
And given that fact
Lex Fridman (59:03.560)
that any non deterministic polynomial time algorithm
Richard Karp (59:07.680)
can be described by a list of such instructions,
Lex Fridman (59:12.920)
you could translate the problem
Richard Karp (59:15.880)
into the language of the satisfiability problem.
Lex Fridman (59:19.120)
Is that amazing to you, by the way,
Richard Karp (59:20.360)
if you take yourself back
Lex Fridman (59:21.320)
when you were first thinking about the space of problems?
Lex Fridman (59:24.640)
How amazing is that?
Lex Fridman (59:26.720)
It's astonishing.
Richard Karp (59:27.920)
When you look at Cook's proof,
Lex Fridman (59:30.320)
it's not too difficult to sort of figure out
Lex Fridman (59:34.520)
why this is so,
Lex Fridman (59:38.520)
but the implications are staggering.
Richard Karp (59:40.720)
It tells us that this, of all the problems in NP,
Lex Fridman (59:46.240)
all the problems where solutions are easy to check,
Richard Karp (59:49.720)
they can all be rewritten
Lex Fridman (59:53.320)
in terms of the satisfiability problem.
Richard Karp (59:59.280)
Yeah, it's adding so much more weight
🔗 相关节目
Grant Sanderson: Math, Manim, Neural Networks & Teaching with 3Blue1Brown
Grant Sanderson
Luís and João Batalha: Fermat’s Library and the Art of Studying Papers
Luís and João Batalha
Andrew Huberman: Sleep, Dreams, Creativity & the Limits of the Human Mind
Andrew Huberman
Andrew Ng: Deep Learning, Education, and Real-World AI
Andrew Ng