back to index## Richard 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.