back to indexRichard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111
link |
The following is a conversation with Richard Karp,
link |
a professor at Berkeley and one of the most important figures
link |
in the history of theoretical computer science.
link |
In 1985, he received the Turing Award
link |
for his research in the theory of algorithms,
link |
including the development of the Admirons Karp algorithm
link |
for solving the max flow problem on networks,
link |
Hopcroft Karp algorithm for finding maximum cardinality
link |
matchings in bipartite graphs,
link |
and his landmark paper in complexity theory
link |
called Reduceability Among Combinatorial Problems,
link |
in which he proved 21 problems to be NP complete.
link |
This paper was probably the most important catalyst
link |
in the explosion of interest in the study of NP completeness
link |
and the P versus NP problem in general.
link |
Quick summary of the ads.
link |
Two sponsors, 8sleep mattress and Cash App.
link |
Please consider supporting this podcast
link |
by going to 8sleep.com slash Lex
link |
and downloading Cash App and using code LexPodcast.
link |
Click the links, buy the stuff.
link |
It really is the best way to support this podcast.
link |
If you enjoy this thing, subscribe on YouTube,
link |
review it with five stars on Apple Podcast,
link |
support it on Patreon,
link |
or connect with me on Twitter at Lex Friedman.
link |
As usual, I'll do a few minutes of ads now
link |
and never any ads in the middle
link |
that can break the flow of the conversation.
link |
This show is sponsored by 8sleep and its Pod Pro mattress
link |
that you can check out at 8sleep.com slash Lex
link |
It controls temperature with an app.
link |
It can cool down to as low as 55 degrees
link |
on each side of the bed separately.
link |
Research shows that temperature has a big impact
link |
on the quality of our sleep.
link |
Anecdotally, it's been a game changer for me.
link |
It's been a couple of weeks now.
link |
I've just been really enjoying it,
link |
both in the fact that I'm getting better sleep
link |
and that it's a smart mattress, essentially.
link |
I kind of imagine this being the early days
link |
of artificial intelligence being a part
link |
of every aspect of our lives.
link |
And certainly infusing AI in one of the most important
link |
aspects of life, which is sleep,
link |
I think has a lot of potential for being beneficial.
link |
The Pod Pro is packed with sensors that track heart rate,
link |
heart rate variability, and respiratory rate,
link |
showing it all in their app.
link |
The app's health metrics are amazing,
link |
but the cooling alone is honestly worth the money.
link |
I don't always sleep, but when I do,
link |
I choose the 8th Sleep Pod Pro mattress.
link |
Check it out at 8thSleep.com slash Lex to get $200 off.
link |
And remember, just visiting the site
link |
and considering the purchase helps convince the folks
link |
at 8th Sleep that this silly old podcast
link |
is worth sponsoring in the future.
link |
This show is also presented by the great
link |
and powerful Cash App,
link |
the number one finance app in the App Store.
link |
When you get it, use code LEXPODCAST.
link |
Cash App lets you send money to friends,
link |
buy Bitcoin, and invest in the stock market
link |
with as little as $1.
link |
It's one of the best designed interfaces
link |
of an app that I've ever used.
link |
To me, good design is when everything is easy and natural.
link |
Bad design is when the app gets in the way,
link |
either because it's buggy,
link |
or because it tries too hard to be helpful.
link |
I'm looking at you, Clippy, from Microsoft,
link |
even though I love you.
link |
Anyway, there's a big part of my brain and heart
link |
that loves to design things
link |
and also to appreciate great design by others.
link |
So again, if you get Cash App from the App Store
link |
or Google Play and use the code LEXPODCAST,
link |
you get $10, and Cash App will also donate $10 to FIRST,
link |
an organization that is helping to advance
link |
robotics and STEM education
link |
for young people around the world.
link |
And now, here's my conversation with Richard Karp.
link |
You wrote that at the age of 13,
link |
you were first exposed to plane geometry
link |
and was wonderstruck by the power and elegance
link |
of form of proofs.
link |
Are there problems, proofs, properties, ideas
link |
in plane geometry that from that time
link |
that you remember being mesmerized by
link |
or just enjoying to go through to prove various aspects?
link |
So Michael Rabin told me this story
link |
about an experience he had when he was a young student
link |
who was tossed out of his classroom for bad behavior
link |
and was wandering through the corridors of his school
link |
and came upon two older students
link |
who were studying the problem of finding
link |
the shortest distance between two nonoverlapping circles.
link |
And Michael thought about it and said,
link |
you take the straight line between the two centers
link |
and the segment between the two circles is the shortest
link |
because a straight line is the shortest distance
link |
between the two centers.
link |
And any other line connecting the circles
link |
would be on a longer line.
link |
And I thought, and he thought, and I agreed
link |
that this was just elegance, the pure reasoning
link |
could come up with such a result.
link |
Certainly the shortest distance
link |
from the two centers of the circles is a straight line.
link |
Could you once again say what's the next step in that proof?
link |
Well, any segment joining the two circles,
link |
if you extend it by taking the radius on each side,
link |
you get a path with three edges
link |
which connects the two centers.
link |
And this has to be at least as long as the shortest path,
link |
which is the straight line.
link |
The straight line, yeah.
link |
Wow, yeah, that's quite simple.
link |
So what is it about that elegance
link |
that you just find compelling?
link |
Well, just that you could establish a fact
link |
about geometry beyond dispute by pure reasoning.
link |
I also enjoy the challenge of solving puzzles
link |
in plain geometry.
link |
It was much more fun than the earlier mathematics courses
link |
which were mostly about arithmetic operations
link |
and manipulating them.
link |
Was there something about geometry itself,
link |
the slightly visual component of it?
link |
Oh, yes, absolutely,
link |
although I lacked three dimensional vision.
link |
I wasn't very good at three dimensional vision.
link |
You mean being able to visualize three dimensional objects?
link |
Three dimensional objects or surfaces,
link |
hyperplanes and so on.
link |
So there I didn't have an intuition.
link |
But for example, the fact that the sum of the angles
link |
of a triangle is 180 degrees is proved convincingly.
link |
And it comes as a surprise that that can be done.
link |
Why is that surprising?
link |
Well, it is a surprising idea, I suppose.
link |
Why is that proved difficult?
link |
It's not, that's the point.
link |
It's so easy and yet it's so convincing.
link |
Do you remember what is the proof that it adds up to 180?
link |
You start at a corner and draw a line
link |
parallel to the opposite side.
link |
And that line sort of trisects the angle
link |
between the other two sides.
link |
And you get a half plane which has to add up to 180 degrees.
link |
It has to add up to 180 degrees and it consists
link |
in the angles by the equality of alternate angles.
link |
You get a correspondence between the angles
link |
created along the side of the triangle
link |
and the three angles of the triangle.
link |
Has geometry had an impact on when you look into the future
link |
of your work with combinatorial algorithms?
link |
Has it had some kind of impact in terms of, yeah,
link |
being able, the puzzles, the visual aspects
link |
that were first so compelling to you?
link |
Not Euclidean geometry particularly.
link |
I think I use tools like linear programming
link |
and integer programming a lot.
link |
But those require high dimensional visualization
link |
and so I tend to go by the algebraic properties.
link |
Right, you go by the linear algebra
link |
and not by the visualization.
link |
Well, the interpretation in terms of, for example,
link |
finding the highest point on a polyhedron
link |
as in linear programming is motivating.
link |
But again, I don't have the high dimensional intuition
link |
that would particularly inform me
link |
so I sort of lean on the algebra.
link |
So to linger on that point,
link |
what kind of visualization do you do
link |
when you're trying to think about,
link |
we'll get to combinatorial algorithms,
link |
but just algorithms in general.
link |
What's inside your mind
link |
when you're thinking about designing algorithms?
link |
Or even just tackling any mathematical problem?
link |
Well, I think that usually an algorithm
link |
involves a repetition of some inner loop
link |
and so I can sort of visualize the distance
link |
from the desired solution as iteratively reducing
link |
until you finally hit the exact solution.
link |
And try to take steps that get you closer to the.
link |
Try to take steps that get closer
link |
and having the certainty of converging.
link |
So it's basically the mechanics of the algorithm
link |
is often very simple,
link |
but especially when you're trying something out
link |
So for example, I did some work
link |
on the traveling salesman problem
link |
and I could see there was a particular function
link |
that had to be minimized
link |
and it was fascinating to see the successive approaches
link |
to the minimum, to the optimum.
link |
You mean, so first of all,
link |
traveling salesman problem is where you have to visit
link |
every city without ever, the only ones.
link |
Yeah, that's right.
link |
Find the shortest path through a set of cities.
link |
Yeah, which is sort of a canonical standard,
link |
a really nice problem that's really hard.
link |
Right, exactly, yes.
link |
So can you say again what was nice
link |
about being able to think about the objective function there
link |
and maximizing it or minimizing it?
link |
Well, just that as the algorithm proceeded,
link |
you were making progress, continual progress,
link |
and eventually getting to the optimum point.
link |
So there's two parts, maybe.
link |
Maybe you can correct me.
link |
First is like getting an intuition
link |
about what the solution would look like
link |
and or even maybe coming up with a solution
link |
and two is proving that this thing
link |
is actually going to be pretty good.
link |
What part is harder for you?
link |
Where's the magic happen?
link |
Is it in the first sets of intuitions
link |
or is it in the messy details of actually showing
link |
that it is going to get to the exact solution
link |
and it's gonna run at a certain complexity?
link |
Well, the magic is just the fact
link |
that the gap from the optimum decreases monotonically
link |
and you can see it happening
link |
and various metrics of what's going on
link |
are improving all along until finally you hit the optimum.
link |
Perhaps later we'll talk about the assignment problem
link |
and I can illustrate.
link |
It illustrates a little better.
link |
Now zooming out again, as you write,
link |
Don Knuth has called attention to a breed of people
link |
who derive great aesthetic pleasure
link |
from contemplating the structure of computational processes.
link |
So Don calls these folks geeks
link |
and you write that you remember the moment
link |
you realized you were such a person,
link |
you were shown the Hungarian algorithm
link |
to solve the assignment problem.
link |
So perhaps you can explain what the assignment problem is
link |
and what the Hungarian algorithm is.
link |
So in the assignment problem,
link |
you have n boys and n girls
link |
and you are given the desirability of,
link |
or the cost of matching the ith boy
link |
with the jth girl for all i and j.
link |
You're given a matrix of numbers
link |
and you want to find the one to one matching
link |
of the boys with the girls
link |
such that the sum of the associated costs will be minimized.
link |
So the best way to match the boys with the girls
link |
or men with jobs or any two sets.
link |
Any possible matching is possible or?
link |
Yeah, all one to one correspondences are permissible.
link |
If there is a connection that is not allowed,
link |
then you can think of it as having an infinite cost.
link |
So what you do is to depend on the observation
link |
that the identity of the optimal assignment
link |
or as we call it, the optimal permutation
link |
is not changed if you subtract a constant
link |
from any row or column of the matrix.
link |
You can see that the comparison
link |
between the different assignments is not changed by that.
link |
Because if you decrease a particular row,
link |
all the elements of a row by some constant,
link |
all solutions decrease by an amount equal to that constant.
link |
So the idea of the algorithm is to start with a matrix
link |
of non negative numbers and keep subtracting
link |
from rows or from columns.
link |
Subtracting from rows or entire columns
link |
in such a way that you subtract the same constant
link |
from all the elements of that row or column
link |
while maintaining the property
link |
that all the elements are non negative.
link |
Yeah, and so what you have to do
link |
is find small moves which will decrease the total cost
link |
while subtracting constants from rows or columns.
link |
And there's a particular way of doing that
link |
by computing the kind of shortest path
link |
through the elements in the matrix.
link |
And you just keep going in this way
link |
until you finally get a full permutation of zeros
link |
while the matrix is non negative
link |
and then you know that that has to be the cheapest.
link |
Is that as simple as it sounds?
link |
So the shortest path of the matrix part.
link |
Yeah, the simplicity lies in how you find,
link |
I oversimplified slightly what you,
link |
you will end up subtracting a constant
link |
from some rows or columns
link |
and adding the same constant back to other rows and columns.
link |
So as not to reduce any of the zero elements,
link |
you leave them unchanged.
link |
But each individual step modifies several rows and columns
link |
by the same amount but overall decreases the cost.
link |
So there's something about that elegance
link |
that made you go aha, this is a beautiful,
link |
like it's amazing that something like this,
link |
something so simple can solve a problem like this.
link |
Yeah, it's really cool.
link |
If I had mechanical ability,
link |
I would probably like to do woodworking
link |
or other activities where you sort of shape something
link |
into something beautiful and orderly
link |
and there's something about the orderly systematic nature
link |
of that iterative algorithm that is pleasing to me.
link |
So what do you think about this idea of geeks
link |
as Don Knuth calls them?
link |
What do you think, is it something specific to a mindset
link |
that allows you to discover the elegance
link |
in computational processes or is this all of us,
link |
can all of us discover this beauty?
link |
Were you born this way?
link |
I always like to play with numbers.
link |
I used to amuse myself by multiplying
link |
by multiplying four digit decimal numbers in my head
link |
and putting myself to sleep by starting with one
link |
and doubling the number as long as I could go
link |
and testing my memory, my ability to retain the information.
link |
And I also read somewhere that you wrote
link |
that you enjoyed showing off to your friends
link |
by I believe multiplying four digit numbers.
link |
Four digit numbers.
link |
Yeah, I had a summer job at a beach resort
link |
outside of Boston and the other employee,
link |
I was the barker at a skee ball game.
link |
I used to sit at a microphone saying come one,
link |
come all, come in and play skee ball,
link |
five cents to play, a nickel to win and so on.
link |
That's what a barker, I wasn't sure if I should know
link |
but barker, that's, so you're the charming,
link |
outgoing person that's getting people to come in.
link |
Yeah, well I wasn't particularly charming
link |
but I could be very repetitious and loud.
link |
And the other employees were sort of juvenile delinquents
link |
who had no academic bent but somehow I found
link |
that I could impress them by performing
link |
this mental arithmetic.
link |
Yeah, there's something to that.
link |
Some of the most popular videos on the internet
link |
is there's a YouTube channel called Numberphile
link |
that shows off different mathematical ideas.
link |
There's still something really profoundly interesting
link |
to people about math, the beauty of it.
link |
Something, even if they don't understand
link |
the basic concept even being discussed,
link |
there's something compelling to it.
link |
What do you think that is?
link |
Any lessons you drew from your early teen years
link |
when you were showing off to your friends with the numbers?
link |
Like what is it that attracts us
link |
to the beauty of mathematics do you think?
link |
The general population, not just the computer scientists
link |
and mathematicians.
link |
I think that you can do amazing things.
link |
You can test whether large numbers are prime.
link |
You can solve little puzzles
link |
about cannibals and missionaries.
link |
And that's a kind of achievement, it's puzzle solving.
link |
And at a higher level, the fact that you can do
link |
this reasoning that you can prove
link |
in an absolutely ironclad way that some of the angles
link |
of a triangle is 180 degrees.
link |
Yeah, it's a nice escape from the messiness
link |
of the real world where nothing can be proved.
link |
So, and we'll talk about it, but sometimes the ability
link |
to map the real world into such problems
link |
where you can't prove it is a powerful step.
link |
It's amazing that we can do it.
link |
Of course, another attribute of geeks
link |
is they're not necessarily endowed
link |
with emotional intelligence, so they can live
link |
in a world of abstractions without having
link |
to master the complexities of dealing with people.
link |
So just to link on the historical note,
link |
as a PhD student in 1955, you joined the computational lab
link |
at Harvard where Howard Aiken had built the Mark I
link |
and the Mark IV computers.
link |
Just to take a step back into that history,
link |
what were those computers like?
link |
The Mark IV filled a large room,
link |
much bigger than this large office
link |
that we were talking in now.
link |
And you could walk around inside it.
link |
There were rows of relays.
link |
You could just walk around the interior
link |
and the machine would sometimes fail because of bugs,
link |
which literally meant flying creatures
link |
landing on the switches.
link |
So I never used that machine for any practical purpose.
link |
The lab eventually acquired one of the earlier
link |
commercial computers.
link |
And this was already in the 60s?
link |
No, in the mid 50s, or late 50s.
link |
There was already commercial computers in the...
link |
Yeah, we had a Univac, a Univac with 2,000 words of storage.
link |
And so you had to work hard to allocate the memory properly
link |
to also the excess time from one word to another
link |
depended on the number of the particular words.
link |
And so there was an art to sort of arranging
link |
the storage allocation to make fetching data rapid.
link |
Were you attracted to this actual physical world
link |
implementation of mathematics?
link |
So it's a mathematical machine that's actually doing
link |
the math physically?
link |
I think I was attracted to the underlying algorithms.
link |
But did you draw any inspiration?
link |
So could you have imagined, like what did you imagine
link |
was the future of these giant computers?
link |
Could you have imagined that 60 years later
link |
we'd have billions of these computers all over the world?
link |
I couldn't imagine that, but there was a sense
link |
in the laboratory that this was the wave of the future.
link |
In fact, my mother influenced me.
link |
She told me that data processing was gonna be really big
link |
and I should get into it.
link |
You're a smart woman.
link |
Yeah, she was a smart woman.
link |
And there was just a feeling that this was going
link |
to change the world, but I didn't think of it
link |
in terms of personal computing.
link |
I had no anticipation that we would be walking around
link |
with computers in our pockets or anything like that.
link |
Did you see computers as tools, as mathematical mechanisms
link |
to analyze sort of the theoretical computer science,
link |
or as the AI folks, which is an entire other community
link |
of dreamers, as something that could one day
link |
have human level intelligence?
link |
Well, AI wasn't very much on my radar.
link |
I did read Turing's paper about the...
link |
The Turing Test, Computing and Intelligence.
link |
Yeah, the Turing test.
link |
What'd you think about that paper?
link |
Was that just like science fiction?
link |
I thought that it wasn't a very good test
link |
because it was too subjective.
link |
So I didn't feel that the Turing test
link |
was really the right way to calibrate
link |
how intelligent an algorithm could be.
link |
But to linger on that, do you think it's,
link |
because you've come up with some incredible tests later on,
link |
tests on algorithms, right, that are like strong,
link |
reliable, robust across a bunch of different classes
link |
of algorithms, but returning to this emotional mess
link |
that is intelligence, do you think it's possible
link |
to come up with a test that's as ironclad
link |
as some of the computational complexity work?
link |
Well, I think the greater question
link |
is whether it's possible to achieve human level intelligence.
link |
Right, so first of all, let me, at the philosophical level,
link |
do you think it's possible to create algorithms
link |
that reason and would seem to us
link |
to have the same kind of intelligence as human beings?
link |
It's an open question.
link |
It seems to me that most of the achievements
link |
have operate within a very limited set of ground rules
link |
and for a very limited, precise task,
link |
which is a quite different situation
link |
from the processes that go on in the minds of humans,
link |
which where they have to sort of function
link |
in changing environments, they have emotions,
link |
they have physical attributes for exploring
link |
their environment, they have intuition,
link |
they have desires, emotions, and I don't see anything
link |
in the current achievements of what's called AI
link |
that come close to that capability.
link |
I don't think there's any computer program
link |
which surpasses a six month old child
link |
in terms of comprehension of the world.
link |
Do you think this complexity of human intelligence,
link |
all the cognitive abilities we have,
link |
all the emotion, do you think that could be reduced one day
link |
or just fundamentally can it be reduced
link |
to a set of algorithms or an algorithm?
link |
So can a Turing machine achieve human level intelligence?
link |
I am doubtful about that.
link |
I guess the argument in favor of it
link |
is that the human brain seems to achieve what we call
link |
intelligence cognitive abilities of different kinds.
link |
And if you buy the premise that the human brain
link |
is just an enormous interconnected set of switches,
link |
so to speak, then in principle, you should be able
link |
to diagnose what that interconnection structure is like,
link |
characterize the individual switches,
link |
and build a simulation outside.
link |
But while that may be true in principle,
link |
that cannot be the way we're eventually
link |
gonna tackle this problem.
link |
That does not seem like a feasible way to go about it.
link |
So there is, however, an existence proof that
link |
if you believe that the brain is just a network of neurons
link |
operating by rules, I guess you could say
link |
that that's an existence proof of the capabilities
link |
of a mechanism, but it would be almost impossible
link |
to acquire the information unless we got enough insight
link |
into the operation of the brain.
link |
But there's so much mystery there.
link |
Do you think, what do you make of consciousness,
link |
for example, as an example of something
link |
we completely have no clue about?
link |
The fact that we have this subjective experience.
link |
Is it possible that this network of,
link |
this circuit of switches is able to create
link |
something like consciousness?
link |
To know its own identity.
link |
Yeah, to know the algorithm, to know itself.
link |
I think if you try to define that rigorously,
link |
you'd have a lot of trouble.
link |
Yeah, that seems to be.
link |
So I know that there are many who believe
link |
that general intelligence can be achieved,
link |
and there are even some who feel certain
link |
that the singularity will come
link |
and we will be surpassed by the machines
link |
which will then learn more and more about themselves
link |
and reduce humans to an inferior breed.
link |
I am doubtful that this will ever be achieved.
link |
Just for the fun of it, could you linger on why,
link |
what's your intuition, why you're doubtful?
link |
So there are quite a few people that are extremely worried
link |
about this existential threat of artificial intelligence,
link |
of us being left behind
link |
by this super intelligent new species.
link |
What's your intuition why that's not quite likely?
link |
Just because none of the achievements in speech
link |
or robotics or natural language processing
link |
or creation of flexible computer assistants
link |
or any of that comes anywhere near close
link |
to that level of cognition.
link |
What do you think about ideas of sort of,
link |
if we look at Moore's Law and exponential improvement
link |
to allow us, that would surprise us?
link |
Sort of our intuition fall apart
link |
with exponential improvement because, I mean,
link |
we're not able to kind of,
link |
we kind of think in linear improvement.
link |
We're not able to imagine a world
link |
that goes from the Mark I computer to an iPhone X.
link |
So do you think we could be really surprised
link |
by the exponential growth?
link |
Or on the flip side, is it possible
link |
that also intelligence is actually way, way, way, way harder,
link |
even with exponential improvement to be able to crack?
link |
I don't think any constant factor improvement
link |
could change things.
link |
I mean, given our current comprehension
link |
of what cognition requires,
link |
it seems to me that multiplying the speed of the switches
link |
by a factor of a thousand or a million
link |
will not be useful until we really understand
link |
the organizational principle behind the network of switches.
link |
Well, let's jump into the network of switches
link |
and talk about combinatorial algorithms if we could.
link |
Let's step back with the very basics.
link |
What are combinatorial algorithms?
link |
And what are some major examples
link |
of problems they aim to solve?
link |
A combinatorial algorithm is one which deals
link |
with a system of discrete objects
link |
that can occupy various states
link |
or take on various values from a discrete set of values
link |
and need to be arranged or selected
link |
in such a way as to achieve some,
link |
to minimize some cost function.
link |
Or to prove the existence
link |
of some combinatorial configuration.
link |
So an example would be coloring the vertices of a graph.
link |
So it's fun to ask one of the greatest
link |
computer scientists of all time
link |
the most basic questions in the beginning of most books.
link |
But for people who might not know,
link |
but in general how you think about it, what is a graph?
link |
A graph, that's simple.
link |
It's a set of points, certain pairs of which
link |
are joined by lines called edges.
link |
And they sort of represent the,
link |
in different applications represent the interconnections
link |
between discrete objects.
link |
So they could be the interactions,
link |
interconnections between switches in a digital circuit
link |
or interconnections indicating the communication patterns
link |
of a human community.
link |
And they could be directed or undirected
link |
and then as you've mentioned before, might have costs.
link |
Right, they can be directed or undirected.
link |
They can be, you can think of them as,
link |
if you think, if a graph were representing
link |
a communication network, then the edge could be undirected
link |
meaning that information could flow along it
link |
in both directions or it could be directed
link |
with only one way communication.
link |
A road system is another example of a graph
link |
with weights on the edges.
link |
And then a lot of problems of optimizing the efficiency
link |
of such networks or learning about the performance
link |
of such networks are the object of combinatorial algorithms.
link |
So it could be scheduling classes at a school
link |
where the vertices, the nodes of the network
link |
are the individual classes and the edges indicate
link |
the constraints which say that certain classes
link |
cannot take place at the same time
link |
or certain teachers are available only for certain classes,
link |
Or I talked earlier about the assignment problem
link |
of matching the boys with the girls
link |
where you have there a graph with an edge
link |
from each boy to each girl with a weight
link |
indicating the cost.
link |
Or in logical design of computers,
link |
you might want to find a set of so called gates,
link |
switches that perform logical functions
link |
which can be interconnected to each other
link |
and perform logical functions which can be interconnected
link |
to realize some function.
link |
So you might ask how many gates do you need
link |
in order for a circuit to give a yes output
link |
if at least a given number of its inputs are ones
link |
and no if fewer are present.
link |
My favorite's probably all the work with network flow.
link |
So anytime you have, I don't know why it's so compelling
link |
but there's something just beautiful about it.
link |
It seems like there's so many applications
link |
and communication networks and traffic flow
link |
that you can map into these and then you could think
link |
of pipes and water going through pipes
link |
and you could optimize it in different ways.
link |
There's something always visually and intellectually
link |
compelling to me about it.
link |
And of course you've done work there.
link |
Yeah, so there the edges represent channels
link |
along which some commodity can flow.
link |
It might be gas, it might be water, it might be information.
link |
Maybe supply chain as well like products being.
link |
Products flowing from one operation to another.
link |
And the edges have a capacity which is the rate
link |
at which the commodity can flow.
link |
And a central problem is to determine
link |
given a network of these channels.
link |
In this case the edges are communication channels.
link |
The challenge is to find the maximum rate
link |
at which the information can flow along these channels
link |
to get from a source to a destination.
link |
And that's a fundamental combinatorial problem
link |
that I've worked on jointly with the scientist Jack Edmonds.
link |
I think we're the first to give a formal proof
link |
that this maximum flow problem through a network
link |
can be solved in polynomial time.
link |
Which I remember the first time I learned that.
link |
Just learning that in maybe even grad school.
link |
I don't think it was even undergrad.
link |
No, algorithm, yeah.
link |
Do network flows get taught in basic algorithms courses?
link |
Okay, so yeah, I remember being very surprised
link |
that max flow is a polynomial time algorithm.
link |
That there's a nice fast algorithm that solves max flow.
link |
So there is an algorithm named after you in Edmonds.
link |
The Edmond Carp algorithm for max flow.
link |
So what was it like tackling that problem
link |
and trying to arrive at a polynomial time solution?
link |
And maybe you can describe the algorithm.
link |
Maybe you can describe what's the running time complexity
link |
Yeah, well, first of all,
link |
what is a polynomial time algorithm?
link |
Perhaps we could discuss that.
link |
So yeah, let's actually just even, yeah.
link |
What is algorithmic complexity?
link |
What are the major classes of algorithm complexity?
link |
So in a problem like the assignment problem
link |
or scheduling schools or any of these applications,
link |
you have a set of input data which might, for example,
link |
be a set of vertices connected by edges
link |
with you're given for each edge the capacity of the edge.
link |
And you have algorithms which are,
link |
think of them as computer programs with operations
link |
such as addition, subtraction, multiplication, division,
link |
comparison of numbers, and so on.
link |
And you're trying to construct an algorithm
link |
based on those operations, which will determine
link |
in a minimum number of computational steps
link |
the answer to the problem.
link |
In this case, the computational step
link |
is one of those operations.
link |
And the answer to the problem is let's say
link |
the configuration of the network
link |
that carries the maximum amount of flow.
link |
And an algorithm is said to run in polynomial time
link |
if as a function of the size of the input,
link |
the number of vertices, the number of edges, and so on,
link |
the number of basic computational steps grows
link |
only as some fixed power of that size.
link |
A linear algorithm would execute a number of steps
link |
linearly proportional to the size.
link |
Quadratic algorithm would be steps proportional
link |
to the square of the size, and so on.
link |
And algorithms whose running time is bounded
link |
by some fixed power of the size
link |
are called polynomial algorithms.
link |
And that's supposed to be relatively fast class
link |
Theoreticians take that to be the definition
link |
of an algorithm being efficient.
link |
And we're interested in which problems can be solved
link |
by such efficient algorithms.
link |
One can argue whether that's the right definition
link |
of efficient because you could have an algorithm
link |
whose running time is the 10,000th power
link |
of the size of the input,
link |
and that wouldn't be really efficient.
link |
And in practice, it's oftentimes reducing
link |
from an N squared algorithm to an N log N
link |
or a linear time is practically the jump
link |
that you wanna make to allow a real world system
link |
to solve a problem.
link |
Yeah, that's also true because especially
link |
as we get very large networks,
link |
the size can be in the millions,
link |
and then anything above N log N
link |
where N is the size would be too much
link |
for a practical solution.
link |
Okay, so that's polynomial time algorithms.
link |
What other classes of algorithms are there?
link |
What's, so that usually they designate polynomials
link |
There's also NP, NP complete and NP hard.
link |
So can you try to disentangle those
link |
by trying to define them simply?
link |
Right, so a polynomial time algorithm
link |
is one whose running time is bounded
link |
by a polynomial in the size of the input.
link |
Then the class of such algorithms is called P.
link |
In the worst case, by the way, we should say, right?
link |
So for every case of the problem.
link |
Yes, that's right, and that's very important
link |
that in this theory, when we measure the complexity
link |
of an algorithm, we really measure the number of steps,
link |
the growth of the number of steps in the worst case.
link |
So you may have an algorithm that runs very rapidly
link |
in most cases, but if there's any case
link |
where it gets into a very long computation,
link |
that would increase the computational complexity
link |
And that's a very important issue
link |
because there are, as we may discuss later,
link |
there are some very important algorithms
link |
which don't have a good standing
link |
from the point of view of their worst case performance
link |
and yet are very effective.
link |
So theoreticians are interested in P,
link |
the class of problem solvable in polynomial time.
link |
Then there's NP, which is the class of problems
link |
which may be hard to solve, but when confronted
link |
with a solution, you can check it in polynomial time.
link |
Let me give you an example there.
link |
So if we look at the assignment problem,
link |
so you have N boys, you have N girls,
link |
the number of numbers that you need to write down
link |
to specify the problem instance is N squared.
link |
And the question is how many steps are needed to solve it?
link |
And Jack Edmonds and I were the first to show
link |
that it could be done in time and cubed.
link |
Earlier algorithms required N to the fourth.
link |
So as a polynomial function of the size of the input,
link |
this is a fast algorithm.
link |
Now to illustrate the class NP, the question is
link |
how long would it take to verify
link |
that a solution is optimal?
link |
So for example, if the input was a graph,
link |
we might want to find the largest clique in the graph
link |
or a clique is a set of vertices such that any vertex,
link |
each vertex in the set is adjacent to each of the others.
link |
So the clique is a complete subgraph.
link |
Yeah, so if it's a Facebook social network,
link |
everybody's friends with everybody else, close clique.
link |
No, that would be what's called a complete graph.
link |
No, I mean within that clique.
link |
Within that clique, yeah.
link |
Yeah, they're all friends.
link |
So a complete graph is when?
link |
Everybody is friendly.
link |
As everybody is friends with everybody, yeah.
link |
So the problem might be to determine whether
link |
in a given graph there exists a clique of a certain size.
link |
Now that turns out to be a very hard problem,
link |
but if somebody hands you a clique and asks you to check
link |
whether it is, hands you a set of vertices
link |
and asks you to check whether it's a clique,
link |
you could do that simply by exhaustively looking
link |
at all of the edges between the vertices and the clique
link |
and verifying that they're all there.
link |
And that's a polynomial time algorithm.
link |
That's a polynomial.
link |
So the problem of finding the clique
link |
appears to be extremely hard,
link |
but the problem of verifying a clique
link |
to see if it reaches a target number of vertices
link |
is easy to verify.
link |
So finding the clique is hard, checking it is easy.
link |
Problems of that nature are called
link |
nondeterministic polynomial time algorithms,
link |
and that's the class NP.
link |
And what about NP complete and NP hard?
link |
Okay, let's talk about problems
link |
where you're getting a yes or no answer
link |
rather than a numerical value.
link |
So either there is a perfect matching
link |
of the boys with the girls or there isn't.
link |
It's clear that every problem in P is also in NP.
link |
If you can solve the problem exactly,
link |
then you can certainly verify the solution.
link |
On the other hand, there are problems in the class NP.
link |
This is the class of problems that are easy to check,
link |
although they may be hard to solve.
link |
It's not at all clear that problems in NP lie in P.
link |
So for example, if we're looking
link |
at scheduling classes at a school,
link |
the fact that you can verify when handed a schedule
link |
for the school, whether it meets all the requirements,
link |
that doesn't mean that you can find the schedule rapidly.
link |
So intuitively, NP, nondeterministic polynomial checking
link |
rather than finding, is going to be harder than,
link |
is going to include, is easier.
link |
Checking is easier, and therefore the class of problems
link |
that can be checked appears to be much larger
link |
than the class of problems that can be solved.
link |
And then you keep adding appears to,
link |
and sort of these additional words that designate
link |
that we don't know for sure yet.
link |
We don't know for sure.
link |
So the theoretical question, which is considered
link |
to be the most central problem
link |
in theoretical computer science,
link |
or at least computational complexity theory,
link |
combinatorial algorithm theory,
link |
the question is whether P is equal to NP.
link |
If P were equal to NP, it would be amazing.
link |
It would mean that every problem
link |
where a solution can be rapidly checked
link |
can actually be solved in polynomial time.
link |
We don't really believe that's true.
link |
If you're scheduling classes at a school,
link |
we expect that if somebody hands you a satisfying schedule,
link |
you can verify that it works.
link |
That doesn't mean that you should be able
link |
to find such a schedule.
link |
So intuitively, NP encompasses a lot more problems than P.
link |
So can we take a small tangent
link |
and break apart that intuition?
link |
So do you, first of all, think that the biggest
link |
sort of open problem in computer science,
link |
maybe mathematics, is whether P equals NP?
link |
Do you think P equals NP,
link |
or do you think P is not equal to NP?
link |
If you had to bet all your money on it.
link |
I would bet that P is unequal to NP,
link |
simply because there are problems
link |
that have been around for centuries
link |
and have been studied intensively in mathematics,
link |
and even more so in the last 50 years
link |
since the P versus NP was stated.
link |
And no polynomial time algorithms have been found
link |
for these easy to check problems.
link |
So one example is a problem that goes back
link |
to the mathematician Gauss,
link |
who was interested in factoring large numbers.
link |
So we know what a number is prime
link |
if it cannot be written as the product
link |
of two or more numbers unequal to one.
link |
So if we can factor a number like 91, it's seven times 13.
link |
But if I give you 20 digit or 30 digit numbers,
link |
you're probably gonna be at a loss
link |
to have any idea whether they can be factored.
link |
So the problem of factoring very large numbers
link |
does not appear to have an efficient solution.
link |
But once you have found the factors,
link |
expressed the number as a product of two smaller numbers,
link |
you can quickly verify that they are factors of the number.
link |
And your intuition is a lot of people finding,
link |
a lot of brilliant people have tried to find algorithms
link |
for this one particular problem.
link |
There's many others like it that are really well studied
link |
and it would be great to find an efficient algorithm for.
link |
Right, and in fact, we have some results
link |
that I was instrumental in obtaining following up on work
link |
by the mathematician Stephen Cook
link |
to show that within the class NP of easy to check problems,
link |
easy to check problems, there's a huge number
link |
that are equivalent in the sense that either all of them
link |
or none of them lie in P.
link |
And this happens only if P is equal to NP.
link |
So if P is unequal to NP, we would also know
link |
that virtually all the standard combinatorial problems,
link |
virtually all the standard combinatorial problems,
link |
if P is unequal to NP, none of them can be solved
link |
in polynomial time.
link |
Can you explain how that's possible
link |
to tie together so many problems in a nice bunch
link |
that if one is proven to be efficient, then all are?
link |
The first and most important stage of progress
link |
was a result by Stephen Cook who showed that a certain problem
link |
called the satisfiability problem of propositional logic
link |
is as hard as any problem in the class P.
link |
So the propositional logic problem is expressed
link |
in terms of expressions involving the logical operations
link |
and, or, and not operating on variables
link |
that can be either true or false.
link |
So an instance of the problem would be some formula
link |
involving and, or, and not.
link |
And the question would be whether there is an assignment
link |
of truth values to the variables in the problem
link |
that would make the formula true.
link |
So for example, if I take the formula A or B
link |
and A or not B and not A or B and not A or not B
link |
and take the conjunction of all four
link |
of those so called expressions,
link |
you can determine that no assignment of truth values
link |
to the variables A and B will allow that conjunction
link |
of what are called clauses to be true.
link |
So that's an example of a formula in propositional logic
link |
involving expressions based on the operations and, or, and not.
link |
That's an example of a problem which is not satisfiable.
link |
There is no solution that satisfies
link |
all of those constraints.
link |
I mean that's like one of the cleanest and fundamental
link |
problems in computer science.
link |
It's like a nice statement of a really hard problem.
link |
It's a nice statement of a really hard problem
link |
and what Cook showed is that every problem in NP
link |
can be reexpressed as an instance
link |
of the satisfiability problem.
link |
So to do that, he used the observation
link |
that a very simple abstract machine
link |
called the Turing machine can be used
link |
to describe any algorithm.
link |
An algorithm for any realistic computer
link |
can be translated into an equivalent algorithm
link |
on one of these Turing machines
link |
which are extremely simple.
link |
So a Turing machine, there's a tape and you can
link |
Yeah, you have data on a tape
link |
and you have basic instructions,
link |
a finite list of instructions which say,
link |
if you're reading a particular symbol on the tape
link |
and you're in a particular state,
link |
then you can move to a different state
link |
and change the state of the number
link |
or the element that you were looking at,
link |
the cell of the tape that you were looking at.
link |
And that was like a metaphor and a mathematical construct
link |
that Turing put together
link |
to represent all possible computation.
link |
All possible computation.
link |
Now, one of these so called Turing machines
link |
is too simple to be useful in practice,
link |
but for theoretical purposes,
link |
we can depend on the fact that an algorithm
link |
for any computer can be translated
link |
into one that would run on a Turing machine.
link |
And then using that fact,
link |
he could sort of describe
link |
any possible non deterministic polynomial time algorithm.
link |
Any algorithm for a problem in NP
link |
could be expressed as a sequence of moves
link |
of the Turing machine described
link |
in terms of reading a symbol on the tape
link |
while you're in a given state
link |
and moving to a new state and leaving behind a new symbol.
link |
And given that fact
link |
that any non deterministic polynomial time algorithm
link |
can be described by a list of such instructions,
link |
you could translate the problem
link |
into the language of the satisfiability problem.
link |
Is that amazing to you, by the way,
link |
if you take yourself back
link |
when you were first thinking about the space of problems?
link |
How amazing is that?
link |
When you look at Cook's proof,
link |
it's not too difficult to sort of figure out
link |
but the implications are staggering.
link |
It tells us that this, of all the problems in NP,
link |
all the problems where solutions are easy to check,
link |
they can all be rewritten
link |
in terms of the satisfiability problem.
link |
Yeah, it's adding so much more weight
link |
to the P equals NP question
link |
because all it takes is to show that one algorithm
link |
So the P versus NP can be re expressed
link |
as simply asking whether the satisfiability problem
link |
of propositional logic is solvable in polynomial time.
link |
I encountered Cook's paper
link |
when he published it in a conference in 1971.
link |
Yeah, so when I saw Cook's paper
link |
and saw this reduction of each of the problems in NP
link |
by a uniform method to the satisfiability problem
link |
of propositional logic,
link |
that meant that the satisfiability problem
link |
was a universal combinatorial problem.
link |
And it occurred to me through experience I had had
link |
in trying to solve other combinatorial problems
link |
that there were many other problems
link |
which seemed to have that universal structure.
link |
And so I began looking for reductions
link |
from the satisfiability to other problems.
link |
And one of the other problems
link |
would be the so called integer programming problem
link |
of determining whether there's a solution
link |
to a set of linear inequalities involving integer variables.
link |
Just like linear programming,
link |
but there's a constraint that the variables
link |
must remain integers.
link |
In fact, must be the zero or one
link |
could only take on those values.
link |
And that makes the problem much harder.
link |
Yes, that makes the problem much harder.
link |
And it was not difficult to show
link |
that the satisfiability problem can be restated
link |
as an integer programming problem.
link |
So can you pause on that?
link |
Was that one of the first mappings that you tried to do?
link |
And how hard is that mapping?
link |
You said it wasn't hard to show,
link |
but that's a big leap.
link |
It is a big leap, yeah.
link |
Well, let me give you another example.
link |
Another problem in NP
link |
is whether a graph contains a clique of a given size.
link |
And now the question is,
link |
can we reduce the propositional logic problem
link |
to the problem of whether there's a clique
link |
of a certain size?
link |
Well, if you look at the propositional logic problem,
link |
it can be expressed as a number of clauses,
link |
each of which is a,
link |
of the form A or B or C,
link |
where A is either one of the variables in the problem
link |
or the negation of one of the variables.
link |
And an instance of the propositional logic problem
link |
can be rewritten using operations of Boolean logic,
link |
can be rewritten as the conjunction of a set of clauses,
link |
the AND of a set of ORs,
link |
where each clause is a disjunction, an OR of variables
link |
or negated variables.
link |
So the question in the satisfiability problem
link |
is whether those clauses can be simultaneously satisfied.
link |
Now, to satisfy all those clauses,
link |
you have to find one of the terms in each clause,
link |
which is going to be true in your truth assignment,
link |
but you can't make the same variable both true and false.
link |
So if you have the variable A in one clause
link |
and you want to satisfy that clause by making A true,
link |
you can't also make the complement of A true
link |
in some other clause.
link |
And so the goal is to make every single clause true
link |
if it's possible to satisfy this,
link |
and the way you make it true is at least...
link |
One term in the clause must be true.
link |
So now we, to convert this problem
link |
to something called the independent set problem,
link |
where you're just sort of asking for a set of vertices
link |
in a graph such that no two of them are adjacent,
link |
sort of the opposite of the clique problem.
link |
So we've seen that we can now express that as
link |
finding a set of terms, one in each clause,
link |
without picking both the variable
link |
and the negation of that variable,
link |
because if the variable is assigned the truth value,
link |
the negated variable has to have the opposite truth value.
link |
And so we can construct a graph where the vertices
link |
are the terms in all of the clauses,
link |
and you have an edge between two terms
link |
if an edge between two occurrences of terms,
link |
either if they're both in the same clause,
link |
because you're only picking one element from each clause,
link |
and also an edge between them if they represent
link |
opposite values of the same variable,
link |
because you can't make a variable both true and false.
link |
And so you get a graph where you have
link |
all of these occurrences of variables,
link |
you have edges, which mean that you're not allowed
link |
to choose both ends of the edge,
link |
either because they're in the same clause
link |
or they're negations of one another.
link |
All right, and that's a, first of all, sort of to zoom out,
link |
that's a really powerful idea that you can take a graph
link |
and connect it to a logic equation somehow,
link |
and do that mapping for all possible formulations
link |
of a particular problem on a graph.
link |
I mean, that still is hard for me to believe.
link |
Yeah, it's hard for me to believe.
link |
It's hard for me to believe that that's possible.
link |
That they're, like, what do you make of that,
link |
that there's such a union of,
link |
there's such a friendship among all these problems across
link |
that somehow are akin to combinatorial algorithms,
link |
that they're all somehow related?
link |
I know it can be proven, but what do you make of it,
link |
Well, that they just have the same expressive power.
link |
You can take any one of them
link |
and translate it into the terms of the other.
link |
The fact that they have the same expressive power
link |
also somehow means that they can be translatable.
link |
Right, and what I did in the 1971 paper
link |
was to take 21 fundamental problems,
link |
the commonly occurring problems of packing,
link |
covering, matching, and so forth,
link |
lying in the class NP,
link |
and show that the satisfiability problem
link |
can be reexpressed as any of those,
link |
that any of those have the same expressive power.
link |
And that was like throwing down the gauntlet
link |
of saying there's probably many more problems like this.
link |
Saying that, look, that they're all the same.
link |
They're all the same, but not exactly.
link |
They're all the same in terms of whether they are
link |
rich enough to express any of the others.
link |
But that doesn't mean that they have
link |
the same computational complexity.
link |
But what we can say is that either all of these problems
link |
or none of them are solvable in polynomial time.
link |
Yeah, so what is NP completeness
link |
and NP hard as classes?
link |
Oh, that's just a small technicality.
link |
So when we're talking about decision problems,
link |
that means that the answer is just yes or no.
link |
There is a clique of size 15
link |
or there's not a clique of size 15.
link |
On the other hand, an optimization problem
link |
would be asking find the largest clique.
link |
The answer would not be yes or no.
link |
So when you're asking for the,
link |
when you're putting a valuation on the different solutions
link |
and you're asking for the one with the highest valuation,
link |
that's an optimization problem.
link |
And there's a very close affinity
link |
between the two kinds of problems.
link |
But the counterpart of being the hardest decision problem,
link |
the hardest yes, no problem,
link |
the counterpart of that is to minimize
link |
or maximize an objective function.
link |
And so a problem that's hardest in the class
link |
when viewed in terms of optimization,
link |
those are called NP hard rather than NP complete.
link |
And NP complete is for decision problems.
link |
And NP complete is for decision problems.
link |
So if somebody shows that P equals NP,
link |
what do you think that proof will look like
link |
if you were to put on yourself,
link |
if it's possible to show that as a proof
link |
or to demonstrate an algorithm?
link |
All I can say is that it will involve concepts
link |
that we do not now have and approaches that we don't have.
link |
Do you think those concepts are out there
link |
in terms of inside complexity theory,
link |
inside of computational analysis of algorithms?
link |
Do you think there's concepts
link |
that are totally outside of the box
link |
that we haven't considered yet?
link |
I think that if there is a proof that P is equal to NP
link |
or that P is unequal to NP,
link |
it'll depend on concepts that are now outside the box.
link |
Now, if that's shown either way, P equals NP or P not,
link |
well, actually P equals NP,
link |
what impact, you kind of mentioned a little bit,
link |
but can you linger on it?
link |
What kind of impact would it have
link |
on theoretical computer science
link |
and perhaps software based systems in general?
link |
Well, I think it would have enormous impact on the world
link |
in either way case.
link |
If P is unequal to NP, which is what we expect,
link |
then we know that for the great majority
link |
of the combinatorial problems that come up,
link |
since they're known to be NP complete,
link |
we're not going to be able to solve them
link |
by efficient algorithms.
link |
However, there's a little bit of hope
link |
in that it may be that we can solve most instances.
link |
All we know is that if a problem is not NP,
link |
then it can't be solved efficiently on all instances.
link |
But basically, if we find that P is unequal to NP,
link |
it will mean that we can't expect always
link |
to get the optimal solutions to these problems.
link |
And we have to depend on heuristics
link |
that perhaps work most of the time
link |
or give us good approximate solutions, but not.
link |
So we would turn our eye towards the heuristics
link |
with a little bit more acceptance and comfort on our hearts.
link |
Okay, so let me ask a romanticized question.
link |
What to you is one of the most
link |
or the most beautiful combinatorial algorithm
link |
in your own life or just in general in the field
link |
that you've ever come across or have developed yourself?
link |
Oh, I like the stable matching problem
link |
or the stable marriage problem very much.
link |
What's the stable matching problem?
link |
Imagine that you want to marry off N boys with N girls.
link |
And each boy has an ordered list
link |
of his preferences among the girls.
link |
His first choice, his second choice,
link |
through her, Nth choice.
link |
And each girl also has an ordering of the boys,
link |
his first choice, second choice, and so on.
link |
And we'll say that a matching,
link |
a one to one matching of the boys with the girls is stable
link |
if there are no two couples in the matching
link |
such that the boy in the first couple
link |
prefers the girl in the second couple to her mate
link |
and she prefers the boy to her current mate.
link |
In other words, if the matching is stable
link |
if there is no pair who want to run away with each other
link |
leaving their partners behind.
link |
Actually, this is relevant to matching residents
link |
with hospitals and some other real life problems,
link |
although not quite in the form that I described.
link |
So it turns out that there is,
link |
for any set of preferences, a stable matching exists.
link |
And moreover, it can be computed
link |
by a simple algorithm
link |
in which each boy starts making proposals to girls.
link |
And if the girl receives the proposal,
link |
she accepts it tentatively,
link |
but she can drop it later
link |
if she gets a better proposal from her point of view.
link |
And the boys start going down their lists
link |
proposing to their first, second, third choices
link |
until stopping when a proposal is accepted.
link |
But the girls meanwhile are watching the proposals
link |
that are coming into them.
link |
And the girl will drop her current partner
link |
if she gets a better proposal.
link |
And the boys never go back through the list?
link |
They never go back, yeah.
link |
So once they've been denied.
link |
They don't try again.
link |
They don't try again
link |
because the girls are always improving their status
link |
as they receive better and better proposals.
link |
The boys are going down their lists starting
link |
with their top preferences.
link |
And one can prove that the process will come to an end
link |
where everybody will get matched with somebody
link |
and you won't have any pair
link |
that want to abscond from each other.
link |
Do you find the proof or the algorithm itself beautiful?
link |
Or is it the fact that with the simplicity
link |
of just the two marching,
link |
I mean the simplicity of the underlying rule
link |
of the algorithm, is that the beautiful part?
link |
And you also have the observation that you might ask
link |
who is better off, the boys who are doing the proposing
link |
or the girls who are reacting to proposals.
link |
And it turns out that it's the boys
link |
who are doing the best.
link |
That is, each boy is doing at least as well
link |
as he could do in any other staple matching.
link |
So there's a sort of lesson for the boys
link |
that you should go out and be proactive
link |
and make those proposals.
link |
I don't know if this is directly mappable philosophically
link |
to our society, but certainly seems
link |
like a compelling notion.
link |
And like you said, there's probably a lot
link |
of actual real world problems that this could be mapped to.
link |
Yeah, well you get complications.
link |
For example, what happens when a husband and wife
link |
want to be assigned to the same hospital?
link |
So you have to take those constraints into account.
link |
And then the problem becomes NP hard.
link |
Why is it a problem for the husband and wife
link |
to be assigned to the same hospital?
link |
No, it's desirable.
link |
Or at least go to the same city.
link |
So you can't, if you're assigning residents to hospitals.
link |
And then you have some preferences
link |
for the husband and the wife or for the hospitals.
link |
The residents have their own preferences.
link |
Residents both male and female have their own preferences.
link |
The hospitals have their preferences.
link |
But if resident A, the boy, is going to Philadelphia,
link |
then you'd like his wife also to be assigned
link |
to a hospital in Philadelphia.
link |
Which step makes it a NP hard problem that you mentioned?
link |
The fact that you have this additional constraint.
link |
That it's not just the preferences of individuals,
link |
but the fact that the two partners to a marriage
link |
have to be assigned to the same place.
link |
I'm being a little dense.
link |
The perfect matching, no, not the perfect,
link |
stable matching is what you referred to.
link |
That's when two partners are trying to.
link |
Okay, what's confusing you is that in the first
link |
interpretation of the problem,
link |
I had boys matching with girls.
link |
In the second interpretation,
link |
you have humans matching with institutions.
link |
With institutions.
link |
I, and there's a coupling between within the,
link |
gotcha, within the humans.
link |
Any added little constraint will make it an NP hard problem.
link |
By the way, the algorithm you mentioned
link |
wasn't one of yours or no?
link |
No, no, that was due to Gale and Shapley
link |
and my friend David Gale passed away
link |
before he could get part of a Nobel Prize,
link |
but his partner Shapley shared in a Nobel Prize
link |
with somebody else for.
link |
For ideas stemming from the stable matching idea.
link |
So you've also have developed yourself
link |
some elegant, beautiful algorithms.
link |
Again, picking your children,
link |
so the Robin Karp algorithm for string searching,
link |
pattern matching, Edmund Karp algorithm for max flows
link |
we mentioned, Hopcroft Karp algorithm for finding
link |
maximum cardinality matchings in bipartite graphs.
link |
Is there ones that stand out to you,
link |
ones you're most proud of or just
link |
whether it's beauty, elegance,
link |
or just being the right discovery development
link |
in your life that you're especially proud of?
link |
I like the Rabin Karp algorithm
link |
because it illustrates the power of randomization.
link |
So the problem there
link |
is to decide whether a given long string of symbols
link |
is to decide whether a given long string of symbols
link |
from some alphabet contains a given word,
link |
whether a particular word occurs
link |
within some very much longer word.
link |
And so the idea of the algorithm
link |
is to associate with the word that we're looking for,
link |
a fingerprint, some number,
link |
or some combinatorial object that describes that word,
link |
and then to look for an occurrence of that same fingerprint
link |
as you slide along the longer word.
link |
And what we do is we associate with each word a number.
link |
So first of all, we think of the letters
link |
that occur in a word as the digits of, let's say,
link |
decimal or whatever base here,
link |
whatever number of different symbols there are.
link |
That's the base of the numbers, yeah.
link |
Right, so every word can then be thought of as a number
link |
with the letters being the digits of that number.
link |
And then we pick a random prime number in a certain range,
link |
and we take that word viewed as a number,
link |
and take the remainder on dividing that number by the prime.
link |
So coming up with a nice hash function.
link |
It's a kind of hash function.
link |
Yeah, it gives you a little shortcut
link |
for that particular word.
link |
Yeah, so that's the...
link |
It's very different than other algorithms of its kind
link |
that we're trying to do search, string matching.
link |
Yeah, which usually are combinatorial
link |
and don't involve the idea of taking a random fingerprint.
link |
And doing the fingerprinting has two advantages.
link |
One is that as we slide along the long word,
link |
digit by digit, we keep a window of a certain size,
link |
the size of the word we're looking for,
link |
and we compute the fingerprint
link |
of every stretch of that length.
link |
And it turns out that just a couple of arithmetic operations
link |
will take you from the fingerprint of one part
link |
to what you get when you slide over by one position.
link |
So the computation of all the fingerprints is simple.
link |
And secondly, it's unlikely if the prime is chosen randomly
link |
from a certain range that you will get two of the segments
link |
in question having the same fingerprint.
link |
And so there's a small probability of error
link |
which can be checked after the fact,
link |
and also the ease of doing the computation
link |
because you're working with these fingerprints
link |
which are remainder's modulo some big prime.
link |
So that's the magical thing about randomized algorithms
link |
is that if you add a little bit of randomness,
link |
it somehow allows you to take a pretty naive approach,
link |
a simple looking approach, and allow it to run extremely well.
link |
So can you maybe take a step back and say
link |
what is a randomized algorithm, this category of algorithms?
link |
Well, it's just the ability to draw a random number
link |
from such, from some range
link |
or to associate a random number with some object
link |
or to draw that random from some set.
link |
So another example is very simple
link |
if we're conducting a presidential election
link |
and we would like to pick the winner.
link |
In principle, we could draw a random sample
link |
of all of the voters in the country.
link |
And if it was of substantial size, say a few thousand,
link |
then the most popular candidate in that group
link |
would be very likely to be the correct choice
link |
that would come out of counting all the millions of votes.
link |
And of course we can't do this because first of all,
link |
everybody has to feel that his or her vote counted.
link |
And secondly, we can't really do a purely random sample
link |
from that population.
link |
And I guess thirdly, there could be a tie
link |
in which case we wouldn't have a significant difference
link |
between two candidates.
link |
But those things aside,
link |
if you didn't have all that messiness of human beings,
link |
you could prove that that kind of random picking
link |
would come up again.
link |
You just said random picking would solve the problem
link |
with a very low probability of error.
link |
Another example is testing whether a number is prime.
link |
So if I wanna test whether 17 is prime,
link |
I could pick any number between one and 17,
link |
raise it to the 16th power modulo 17,
link |
and you should get back the original number.
link |
That's a famous formula due to Fermat about,
link |
it's called Fermat's Little Theorem,
link |
that if you take any number a in the range
link |
zero through n minus one,
link |
and raise it to the n minus 1th power modulo n,
link |
you'll get back the number a if a is prime.
link |
So if you don't get back the number a,
link |
that's a proof that a number is not prime.
link |
And you can show that suitably defined
link |
the probability that you will get a value unequaled,
link |
you will get a violation of Fermat's result is very high.
link |
And so this gives you a way of rapidly proving
link |
that a number is not prime.
link |
It's a little more complicated than that
link |
because there are certain values of n
link |
where something a little more elaborate has to be done,
link |
but that's the basic idea.
link |
Taking an identity that holds for primes,
link |
and therefore, if it ever fails on any instance
link |
for a non prime, you know that the number is not prime.
link |
It's a quick choice, a fast choice,
link |
fast proof that a number is not prime.
link |
Can you maybe elaborate a little bit more
link |
what's your intuition why randomness works so well
link |
and results in such simple algorithms?
link |
Well, the example of conducting an election
link |
where you could take, in theory, you could take a sample
link |
and depend on the validity of the sample
link |
to really represent the whole
link |
is just the basic fact of statistics,
link |
which gives a lot of opportunities.
link |
And I actually exploited that sort of random sampling idea
link |
in designing an algorithm
link |
for counting the number of solutions
link |
that satisfy a particular formula
link |
and propositional logic.
link |
A particular, so some version of the satisfiability problem?
link |
A version of the satisfiability problem.
link |
Is there some interesting insight
link |
that you wanna elaborate on,
link |
like what some aspect of that algorithm
link |
that might be useful to describe?
link |
So you have a collection of formulas
link |
and you want to count the number of solutions
link |
that satisfy at least one of the formulas.
link |
And you can count the number of solutions
link |
that satisfy any particular one of the formulas,
link |
but you have to account for the fact
link |
that that solution might be counted many times
link |
if it solves more than one of the formulas.
link |
And so what you do is you sample from the formulas
link |
according to the number of solutions
link |
that satisfy each individual one.
link |
In that way, you draw a random solution,
link |
but then you correct by looking at
link |
the number of formulas that satisfy that random solution
link |
and don't double count.
link |
So you can think of it this way.
link |
So you have a matrix of zeros and ones
link |
and you wanna know how many columns of that matrix
link |
contain at least one one.
link |
And you can count in each row how many ones there are.
link |
So what you can do is draw from the rows
link |
according to the number of ones.
link |
If a row has more ones, it gets drawn more frequently.
link |
But then if you draw from that row,
link |
you have to go up the column
link |
and looking at where that same one is repeated
link |
in different rows and only count it as a success or a hit
link |
if it's the earliest row that contains the one.
link |
And that gives you a robust statistical estimate
link |
of the total number of columns
link |
that contain at least one of the ones.
link |
So that is an example of the same principle
link |
that was used in studying random sampling.
link |
Another viewpoint is that if you have a phenomenon
link |
that occurs almost all the time,
link |
then if you sample one of the occasions where it occurs,
link |
you're most likely to,
link |
and you're looking for an occurrence,
link |
a random occurrence is likely to work.
link |
So that comes up in solving identities,
link |
solving algebraic identities.
link |
You get two formulas that may look very different.
link |
You wanna know if they're really identical.
link |
What you can do is just pick a random value
link |
and evaluate the formulas at that value
link |
and see if they agree.
link |
And you depend on the fact
link |
that if the formulas are distinct,
link |
then they're gonna disagree a lot.
link |
And so therefore, a random choice
link |
will exhibit the disagreement.
link |
If there are many ways for the two to disagree
link |
and you only need to find one disagreement,
link |
then random choice is likely to yield it.
link |
And in general, so we've just talked
link |
about randomized algorithms,
link |
but we can look at the probabilistic analysis of algorithms.
link |
And that gives us an opportunity to step back
link |
and as you said, everything we've been talking about
link |
is worst case analysis.
link |
Could you maybe comment on the usefulness
link |
and the power of worst case analysis
link |
versus best case analysis, average case, probabilistic?
link |
How do we think about the future
link |
of theoretical computer science, computer science
link |
in the kind of analysis we do of algorithms?
link |
Does worst case analysis still have a place,
link |
an important place?
link |
Or do we want to try to move forward
link |
towards kind of average case analysis?
link |
And what are the challenges there?
link |
So if worst case analysis shows
link |
that an algorithm is always good,
link |
If worst case analysis is used to show that the problem,
link |
that the solution is not always good,
link |
then you have to step back and do something else
link |
to ask how often will you get a good solution?
link |
Just to pause on that for a second,
link |
that's so beautifully put
link |
because I think we tend to judge algorithms.
link |
We throw them in the trash
link |
the moment their worst case is shown to be bad.
link |
Right, and that's unfortunate.
link |
I think a good example is going back
link |
to the satisfiability problem.
link |
There are very powerful programs called SAT solvers
link |
which in practice fairly reliably solve instances
link |
with many millions of variables
link |
that arise in digital design
link |
or in proving programs correct in other applications.
link |
And so in many application areas,
link |
even though satisfiability as we've already discussed
link |
is NP complete, the SAT solvers will work so well
link |
that the people in that discipline
link |
tend to think of satisfiability as an easy problem.
link |
So in other words, just for some reason
link |
that we don't entirely understand,
link |
the instances that people formulate
link |
in designing digital circuits or other applications
link |
are such that satisfiability is not hard to check
link |
and even searching for a satisfying solution
link |
can be done efficiently in practice.
link |
And there are many examples.
link |
For example, we talked about the traveling salesman problem.
link |
So just to refresh our memories,
link |
the problem is you've got a set of cities,
link |
you have pairwise distances between cities
link |
and you want to find a tour through all the cities
link |
that minimizes the total cost of all the edges traversed,
link |
all the trips between cities.
link |
The problem is NP hard,
link |
but people using integer programming codes
link |
together with some other mathematical tricks
link |
can solve geometric instances of the problem
link |
where the cities are, let's say points in the plane
link |
and get optimal solutions to problems
link |
with tens of thousands of cities.
link |
Actually, it'll take a few computer months
link |
to solve a problem of that size,
link |
but for problems of size a thousand or two,
link |
it'll rapidly get optimal solutions,
link |
provably optimal solutions,
link |
even though again, we know that it's unlikely
link |
that the traveling salesman problem
link |
can be solved in polynomial time.
link |
Are there methodologies like rigorous systematic methodologies
link |
for, you said in practice.
link |
In practice, this algorithm's pretty good.
link |
Are there systematic ways of saying
link |
in practice, this algorithm's pretty good?
link |
So in other words, average case analysis.
link |
Or you've also mentioned that average case
link |
kind of requires you to understand what the typical case is,
link |
typical instances, and that might be really difficult.
link |
That's very difficult.
link |
So after I did my original work
link |
on showing all these problems through NP complete,
link |
I looked around for a way to shed some positive light
link |
on combinatorial algorithms.
link |
And what I tried to do was to study problems,
link |
behavior on the average or with high probability.
link |
But I had to make some assumptions
link |
about what's the probability space?
link |
What's the sample space?
link |
What do we mean by typical problems?
link |
That's very hard to say.
link |
So I took the easy way out
link |
and made some very simplistic assumptions.
link |
So I assumed, for example,
link |
that if we were generating a graph
link |
with a certain number of vertices and edges,
link |
then we would generate the graph
link |
by simply choosing one edge at a time at random
link |
until we got the right number of edges.
link |
That's a particular model of random graphs
link |
that has been studied mathematically a lot.
link |
And within that model,
link |
I could prove all kinds of wonderful things,
link |
I and others who also worked on this.
link |
So we could show that we know exactly
link |
how many edges there have to be
link |
in order for there be a so called Hamiltonian circuit.
link |
That's a cycle that visits each vertex exactly once.
link |
We know that if the number of edges
link |
is a little bit more than n log n,
link |
where n is the number of vertices,
link |
then such a cycle is very likely to exist.
link |
And we can give a heuristic
link |
that will find it with high probability.
link |
And the community in which I was working
link |
got a lot of results along these lines.
link |
But the field tended to be rather lukewarm
link |
about accepting these results as meaningful
link |
because we were making such a simplistic assumption
link |
about the kinds of graphs that we would be dealing with.
link |
So we could show all kinds of wonderful things,
link |
it was a great playground, I enjoyed doing it.
link |
But after a while, I concluded that
link |
it didn't have a lot of bite
link |
in terms of the practical application.
link |
Oh the, okay, so there's too much
link |
into the world of toy problems.
link |
But all right, is there a way to find
link |
nice representative real world impactful instances
link |
of a problem on which demonstrate that an algorithm is good?
link |
So this is kind of like the machine learning world,
link |
that's kind of what they at his best tries to do
link |
is find a data set from like the real world
link |
and show the performance, all the conferences
link |
are all focused on beating the performance
link |
of on that real world data set.
link |
Is there an equivalent in complexity analysis?
link |
Not really, Don Knuth started to collect examples
link |
of graphs coming from various places.
link |
So he would have a whole zoo of different graphs
link |
that he could choose from and he could study
link |
the performance of algorithms on different types of graphs.
link |
But there it's really important and compelling
link |
to be able to define a class of graphs.
link |
The actual act of defining a class of graphs
link |
that you're interested in, it seems to be
link |
a non trivial step if we're talking about instances
link |
that we should care about in the real world.
link |
Yeah, there's nothing available there
link |
that would be analogous to the training set
link |
for supervised learning where you sort of assume
link |
that the world has given you a bunch
link |
of examples to work with.
link |
We don't really have that for problems,
link |
for combinatorial problems on graphs and networks.
link |
You know, there's been a huge growth,
link |
a big growth of data sets available.
link |
Do you think some aspect of theoretical computer science
link |
might be contradicting my own question while saying it,
link |
but will there be some aspect,
link |
an empirical aspect of theoretical computer science
link |
which will allow the fact that these data sets are huge,
link |
we'll start using them for analysis.
link |
Sort of, you know, if you want to say something
link |
about a graph algorithm, you might take
link |
a social network like Facebook and looking at subgraphs
link |
of that and prove something about the Facebook graph
link |
and be respected, and at the same time,
link |
be respected in the theoretical computer science community.
link |
That hasn't been achieved yet, I'm afraid.
link |
Is that P equals NP, is that impossible?
link |
Is it impossible to publish a successful paper
link |
in the theoretical computer science community
link |
that shows some performance on a real world data set?
link |
Or is that really just those are two different worlds?
link |
They haven't really come together.
link |
I would say that there is a field
link |
of experimental algorithmics where people,
link |
sometimes they're given some family of examples.
link |
Sometimes they just generate them at random
link |
and they report on performance,
link |
but there's no convincing evidence
link |
that the sample is representative of anything at all.
link |
So let me ask, in terms of breakthroughs
link |
and open problems, what are the most compelling
link |
open problems to you and what possible breakthroughs
link |
do you see in the near term
link |
in terms of theoretical computer science?
link |
Well, there are all kinds of relationships
link |
among complexity classes that can be studied,
link |
just to mention one thing, I wrote a paper
link |
with Richard Lipton in 1979,
link |
where we asked the following question.
link |
If you take a combinatorial problem in NP, let's say,
link |
and you choose, and you pick the size of the problem,
link |
say it's a traveling salesman problem, but of size 52,
link |
and you ask, could you get an efficient,
link |
a small Boolean circuit tailored for that size, 52,
link |
where you could feed the edges of the graph
link |
in as Boolean inputs and get, as an output,
link |
the question of whether or not
link |
there's a tour of a certain length.
link |
And that would, in other words, briefly,
link |
what you would say in that case
link |
is that the problem has small circuits,
link |
polynomial size circuits.
link |
Now, we know that if P is equal to NP,
link |
then, in fact, these problems will have small circuits,
link |
but what about the converse?
link |
Could a problem have small circuits,
link |
meaning that an algorithm tailored to any particular size
link |
could work well, and yet not be a polynomial time algorithm?
link |
That is, you couldn't write it as a single,
link |
uniform algorithm, good for all sizes.
link |
Just to clarify, small circuits
link |
for a problem of particular size,
link |
by small circuits for a problem of particular size,
link |
or even further constraint,
link |
small circuit for a particular...
link |
No, for all the inputs of that size.
link |
Is that a trivial problem for a particular instance?
link |
So, coming up, an automated way
link |
of coming up with a circuit.
link |
I guess that's just an answer.
link |
That would be hard, yeah.
link |
But there's the existential question.
link |
Everybody talks nowadays about existential questions.
link |
Existential challenges.
link |
You could ask the question,
link |
does the Hamiltonian circuit problem
link |
have a small circuit for every size,
link |
for each size, a different small circuit?
link |
In other words, could you tailor solutions
link |
depending on the size, and get polynomial size?
link |
Even if P is not equal to NP.
link |
That would be fascinating if that's true.
link |
Yeah, what we proved is that if that were possible,
link |
then something strange would happen in complexity theory.
link |
Some high level class which I could briefly describe,
link |
something strange would happen.
link |
So, I'll take a stab at describing what I mean.
link |
Sure, let's go there.
link |
So, we have to define this hierarchy
link |
in which the first level of the hierarchy is P,
link |
and the second level is NP.
link |
NP involves statements of the form
link |
there exists a something such that something holds.
link |
So, for example, there exists the coloring
link |
such that a graph can be colored
link |
with only that number of colors.
link |
Or there exists a Hamiltonian circuit.
link |
There's a statement about this graph.
link |
Yeah, so the NP deals with statements of that kind,
link |
that there exists a solution.
link |
Now, you could imagine a more complicated expression
link |
which says for all x there exists a y
link |
such that some proposition holds involving both x and y.
link |
So, that would say, for example, in game theory,
link |
for all strategies for the first player,
link |
there exists a strategy for the second player
link |
such that the first player wins.
link |
That would be at the second level of the hierarchy.
link |
The third level would be there exists an A
link |
such that for all B there exists a C,
link |
that something holds.
link |
And you could imagine going higher and higher
link |
And you'd expect that the complexity classes
link |
that correspond to those different cases
link |
would get bigger and bigger.
link |
What do you mean by bigger and bigger?
link |
They'd get harder and harder to solve.
link |
Harder and harder, right.
link |
Harder and harder to solve.
link |
And what Lipton and I showed was
link |
that if NP had small circuits,
link |
then this hierarchy would collapse down
link |
to the second level.
link |
In other words, you wouldn't get any more mileage
link |
by complicating your expressions with three quantifiers
link |
or four quantifiers or any number.
link |
I'm not sure what to make of that exactly.
link |
Well, I think it would be evidence
link |
that NP doesn't have small circuits
link |
because something so bizarre would happen.
link |
But again, it's only evidence, not proof.
link |
Well, yeah, that's not even evidence
link |
because you're saying P is not equal to NP
link |
because something bizarre has to happen.
link |
I mean, that's proof by the lack of bizarreness
link |
But it seems like just the very notion
link |
of P equals NP would be bizarre.
link |
So any way you arrive at, there's no way.
link |
You have to fight the dragon at some point.
link |
Well, anyway, for whatever it's worth,
link |
that's what we proved.
link |
So that's a potential space of interesting problems.
link |
Let me ask you about this other world
link |
that of machine learning, of deep learning.
link |
What's your thoughts on the history
link |
and the current progress of machine learning field
link |
that's often progressed sort of separately
link |
as a space of ideas and space of people
link |
than the theoretical computer science
link |
or just even computer science world?
link |
Yeah, it's really very different
link |
from the theoretical computer science world
link |
because the results about it,
link |
algorithmic performance tend to be empirical.
link |
It's more akin to the world of SAT solvers
link |
where we observe that for formulas arising in practice,
link |
the solver does well.
link |
So it's of that type.
link |
We're moving into the empirical evaluation of algorithms.
link |
Now, it's clear that there've been huge successes
link |
in image processing, robotics,
link |
natural language processing, a little less so,
link |
but across the spectrum of game playing is another one.
link |
There've been great successes and one of those effects
link |
is that it's not too hard to become a millionaire
link |
if you can get a reputation in machine learning
link |
and there'll be all kinds of companies
link |
that will be willing to offer you the moon
link |
because they think that if they have AI at their disposal,
link |
then they can solve all kinds of problems.
link |
But there are limitations.
link |
One is that the solutions that you get
link |
to supervise learning problems
link |
through convolutional neural networks
link |
seem to perform amazingly well
link |
even for inputs that are outside the training set.
link |
But we don't have any theoretical understanding
link |
of why that's true.
link |
Secondly, the solutions, the networks that you get
link |
are very hard to understand
link |
and so very little insight comes out.
link |
So yeah, yeah, they may seem to work on your training set
link |
and you may be able to discover whether your photos occur
link |
in a different sample of inputs or not,
link |
but we don't really know what's going on.
link |
We don't know the features that distinguish the photographs
link |
or the objects are not easy to characterize.
link |
Well, it's interesting because you mentioned
link |
coming up with a small circuit to solve
link |
a particular size problem.
link |
It seems that neural networks are kind of small circuits.
link |
But they're not programs.
link |
Sort of like the things you've designed
link |
are algorithms, programs, algorithms.
link |
Neural networks aren't able to develop algorithms
link |
to solve a problem.
link |
Well, they are algorithms.
link |
It's just that they're...
link |
But sort of, yeah, it could be a semantic question,
link |
but there's not a algorithmic style manipulation
link |
Perhaps you could argue there is.
link |
It feels a lot more like a function of the input.
link |
Yeah, it's a function.
link |
It's a computable function.
link |
Once you have the network,
link |
you can simulate it on a given input
link |
and figure out the output.
link |
But if you're trying to recognize images,
link |
then you don't know what features of the image
link |
are really being determinant of what the circuit is doing.
link |
The circuit is sort of very intricate
link |
and it's not clear that the simple characteristics
link |
that you're looking for,
link |
the edges of the objects or whatever they may be,
link |
they're not emerging from the structure of the circuit.
link |
Well, it's not clear to us humans,
link |
but it's clear to the circuit.
link |
Yeah, well, right.
link |
I mean, it's not clear to sort of the elephant
link |
how the human brain works,
link |
but it's clear to us humans,
link |
we can explain to each other our reasoning
link |
and that's why the cognitive science
link |
and psychology field exists.
link |
Maybe the whole thing of being explainable to humans
link |
is a little bit overrated.
link |
I guess you can say the same thing about our brain
link |
that when we perform acts of cognition,
link |
we have no idea how we do it really.
link |
We do though, I mean, at least for the visual system,
link |
the auditory system and so on,
link |
we do get some understanding of the principles
link |
that they operate under,
link |
but for many deeper cognitive tasks, we don't have that.
link |
Let me ask, you've also been doing work on bioinformatics.
link |
Does it amaze you that the fundamental building blocks?
link |
So if we take a step back and look at us humans,
link |
the building blocks used by evolution
link |
to build us intelligent human beings
link |
is all contained there in our DNA.
link |
It's amazing and what's really amazing
link |
is that we are beginning to learn how to edit DNA,
link |
which is very, very, very fascinating.
link |
This ability to take a sequence,
link |
find it in the genome and do something to it.
link |
I mean, that's really taking our biological systems
link |
towards the world of algorithms.
link |
Yeah, but it raises a lot of questions.
link |
You have to distinguish between doing it on an individual
link |
or doing it on somebody's germline,
link |
which means that all of their descendants will be affected.
link |
So that's like an ethical.
link |
Yeah, so it raises very severe ethical questions.
link |
And even doing it on individuals,
link |
there's a lot of hubris involved
link |
that you can assume that knocking out a particular gene
link |
is gonna be beneficial
link |
because you don't know what the side effects
link |
So we have this wonderful new world of gene editing,
link |
which is very, very impressive
link |
and it could be used in agriculture,
link |
it could be used in medicine in various ways.
link |
But very serious ethical problems arise.
link |
What are to you the most interesting places
link |
where algorithms, sort of the ethical side
link |
is an exceptionally challenging thing
link |
that I think we're going to have to tackle
link |
with all of genetic engineering.
link |
But on the algorithmic side,
link |
there's a lot of benefit that's possible.
link |
So is there areas where you see exciting possibilities
link |
for algorithms to help model, optimize,
link |
study biological systems?
link |
Yeah, I mean, we can certainly analyze genomic data
link |
to figure out which genes are operative in the cell
link |
and under what conditions
link |
and which proteins affect one another,
link |
which proteins physically interact.
link |
We can sequence proteins and modify them.
link |
Is there some aspect of that
link |
that's a computer science problem
link |
or is that still fundamentally a biology problem?
link |
Well, it's a big data,
link |
it's a statistical big data problem for sure.
link |
So the biological data sets are increasing,
link |
our ability to study our ancestry,
link |
to study the tendencies towards disease,
link |
to personalize treatment according to what's in our genomes
link |
and what tendencies for disease we have,
link |
to be able to predict what troubles might come upon us
link |
in the future and anticipate them,
link |
to understand whether you,
link |
for a woman, whether her proclivity for breast cancer
link |
is so strong enough that she would want
link |
to take action to avoid it.
link |
You dedicate your 1985 Turing Award lecture
link |
to the memory of your father.
link |
What's your fondest memory of your dad?
link |
Seeing him standing in front of a class at the blackboard,
link |
drawing perfect circles by hand
link |
and showing his ability to attract the interest
link |
of the motley collection of eighth grade students
link |
that he was teaching.
link |
When did you get a chance to see him
link |
draw the perfect circles?
link |
On rare occasions, I would get a chance
link |
to sneak into his classroom and observe him.
link |
And I think he was at his best in the classroom.
link |
I think he really came to life and had fun,
link |
not only teaching, but engaging in chit chat
link |
with the students and ingratiating himself
link |
with the students.
link |
And what I inherited from that is the great desire
link |
I retired recently and a lot of my former students came,
link |
students with whom I had done research
link |
or who had read my papers or who had been in my classes.
link |
And when they talked about me,
link |
they talked not about my 1979 paper or 1992 paper,
link |
but about what came away in my classes.
link |
And not just the details, but just the approach
link |
and the manner of teaching.
link |
And so I sort of take pride in the,
link |
at least in my early years as a faculty member at Berkeley,
link |
I was exemplary in preparing my lectures
link |
and I always came in prepared to the teeth,
link |
and able therefore to deviate according
link |
to what happened in the class,
link |
and to really provide a model for the students.
link |
So is there advice you can give out for others
link |
on how to be a good teacher?
link |
So preparation is one thing you've mentioned,
link |
being exceptionally well prepared,
link |
but there are other things,
link |
pieces of advice that you can impart?
link |
Well, the top three would be preparation, preparation,
link |
Why is preparation so important, I guess?
link |
It's because it gives you the ease
link |
to deal with any situation that comes up in the classroom.
link |
And if you discover that you're not getting through one way,
link |
you can do it another way.
link |
If the students have questions,
link |
you can handle the questions.
link |
Ultimately, you're also feeling the crowd,
link |
the students of what they're struggling with,
link |
what they're picking up,
link |
just looking at them through the questions,
link |
but even just through their eyes.
link |
Yeah, that's right.
link |
And because of the preparation, you can dance.
link |
You can dance, you can say it another way,
link |
or give it another angle.
link |
Are there, in particular, ideas and algorithms
link |
of computer science that you find
link |
were big aha moments for students,
link |
where they, for some reason, once they got it,
link |
it clicked for them and they fell in love
link |
with computer science?
link |
Or is it individual, is it different for everybody?
link |
It's different for everybody.
link |
You have to work differently with students.
link |
Some of them just don't need much influence.
link |
They're just running with what they're doing
link |
and they just need an ear now and then.
link |
Others need a little prodding.
link |
Others need to be persuaded to collaborate among themselves
link |
rather than working alone.
link |
They have their personal ups and downs,
link |
so you have to deal with each student as a human being
link |
and bring out the best.
link |
Humans are complicated.
link |
Perhaps a silly question.
link |
If you could relive a moment in your life outside of family
link |
because it made you truly happy,
link |
or perhaps because it changed the direction of your life
link |
in a profound way, what moment would you pick?
link |
I was kind of a lazy student as an undergraduate,
link |
and even in my first year in graduate school.
link |
And I think it was when I started doing research,
link |
I had a couple of summer jobs where I was able to contribute
link |
and I had an idea.
link |
And then there was one particular course
link |
on mathematical methods and operations research
link |
where I just gobbled up the material
link |
and I scored 20 points higher than anybody else in the class
link |
then came to the attention of the faculty.
link |
And it made me realize that I had some ability
link |
that I was going somewhere.
link |
You realize you're pretty good at this thing.
link |
I don't think there's a better way to end it, Richard.
link |
It was a huge honor.
link |
Thank you for decades of incredible work.
link |
Thank you for talking to me.
link |
Thank you, it's been a great pleasure.
link |
You're a superb interviewer.
link |
Thanks for listening to this conversation with Richard Karp.
link |
And thank you to our sponsors, 8sleep and Cash App.
link |
Please consider supporting this podcast
link |
by going to 8sleep.com slash Lex
link |
to check out their awesome mattress
link |
and downloading Cash App and using code LexPodcast.
link |
Click the links, buy the stuff,
link |
even just visiting the site
link |
but also considering the purchase.
link |
Helps them know that this podcast
link |
is worth supporting in the future.
link |
It really is the best way to support this journey I'm on.
link |
If you enjoy this thing, subscribe on YouTube,
link |
review it with Five Stars and Apple Podcast,
link |
support it on Patreon, connect with me on Twitter
link |
at Lex Friedman if you can figure out how to spell that.
link |
And now let me leave you with some words from Isaac Asimov.
link |
I do not fear computers.
link |
I fear lack of them.
link |
Thank you for listening and hope to see you next time.