Kind: captions
Language: en
the following is a conversation with
richard carp a professor at berkeley
and one of the most important figures in
the history
of theoretical computer science in 1985
he received the touring award for his
research in the theory of algorithms
including the development of the
admirance carp algorithm
for solving the max flow problem on
networks
hopcroft corp algorithm for finding
maximum
cardinality matchings in bipartite
graphs and
his landmark paper and complexity theory
called reducibility
among combinatorial problems in which he
proved
21 problems to be np complete this paper
was probably the most
important catalyst in the explosion of
interest in the study of np completeness
and the p versus np problem in general
quick summary of the ads two sponsors a
sleep mattress
and cash app please consider supporting
this podcast
by going to asleep.com lex
and downloading cash app and using code
lex
podcast click the links buy the stuff it
really is the best way to support this
podcast
if you enjoy this thing subscribe on
youtube review it with 5 stars on apple
podcast
support it on patreon or connect with me
on twitter at lex friedman
as usual i'll do a few minutes of as now
and never any ads in the middle that can
break the flow of the conversation
this show is sponsored by eight sleep
and it's pod pro mattress that you can
check out
at asleep.com lex to get 200
off it controls temperature with an app
it can cool down to as low as 55 degrees
and each side of the bed separately
research shows the temperature has a big
impact on the quality of our sleep
anecdotally it's been a game changer for
me i love it
it's been a couple weeks now i just been
really enjoying it
both in the fact that i'm getting better
sleep and then it's a
smart mattress essentially i kind of
imagine this being the early days of
artificial intelligence being a part of
every aspect of our lives
and certainly infusing ai in one of the
most important aspects of life which is
sleep
i think has a lot of potential for being
beneficial
the pod pro is packed with sensors that
track heart rate
heart rate variability and respiratory
rate
showing it all in their app the app's
health metrics are amazing
but the cooling alone is honestly worth
the money i don't always sleep
but when i do i choose the a-sleep pod
pro mattress
check it out at 8sleep.com to get
two hundred dollars off and remember
just visiting the site and considering
the purchase
helps convince the folks at asleep that
this silly old podcast is worth
sponsoring in the future
this show is also presented by the great
and powerful cash app the number one
finance app in the app store
when you get it use code lex podcast
cash app lets you send money to friends
buy bitcoin and invest in the stock
market with as little as one dollar
it's one of the best designed interfaces
of an app that i've ever used
to me good design is when everything is
easy and natural
bad design is when the app gets in the
way either because it's buggy
or because it tries too hard to be
helpful i'm looking at you clippy from
microsoft
even though i love you anyway there's a
big part of my brain and heart that
loves to design things
and also to appreciate great design by
others so again
if you get cash out from the app store
google play and use the code
lex podcast you get ten dollars and cash
app will also donate ten dollars to
first
an organization that is helping to
advance robotics and stem education
for young people around the world and
now
here's my conversation with richard carp
you wrote that at the age of 13 you were
first exposed to plain geometry
and was wonder struck by the power and
elegance of formal proofs
are there problems proofs properties
ideas and plain geometry that
from that time that you remember being
mesmerized by or just
enjoying to go through to prove
various aspects so michael rabin told me
this story
about an experience he had when he was a
young student
who was ex tossed out of his classroom
for bad behavior and was wandering
through the corridors of his school
and came upon two older students
who were studying the problem of finding
the shortest distance between
two non-overlapping circles
and michael thought about it and said
you take the straight line between the
two centers
and the segment between the two circles
is the shortest
because a straight line is the shortest
distance between the two centers
and any other line connecting the
circles would be
on a longer line and i thought
and he thought and i agreed that this
was just
elegant that pure reasoning could come
up with
such a result certainly the the shortest
distance from the two centers of the
circles
is a straight line could you once again
say
what's the next step in that proof well
any
any segment joining the the two
circles if you extend it
by taking the radius on each side
you get a segment with a path with three
edges which connects the two centers
and this has to be at least as long as
the shortest path which is the straight
line the straight line
yeah wow yeah that is that's quite
quite simple so what what is it about
that elegance that
you just find uh compelling well just
that you could
establish a a fact
about geometry beyond dispute by pure
reasoning
i i also enjoy the challenge of
solving puzzles in plain geometry it was
much more fun
than the earlier mathematics courses
which were mostly about
arithmetic operations and manipulating
them
was was there something about geometry
itself
the slightly visual component of it
yes absolutely although i lacked
three-dimensional vision i wasn't very
good at
three-dimensional vision you mean being
able to visualize three-dimensional
objects
three-dimensional objects or or um
surfaces hyperplanes and so on um
so so there there i didn't have an
intuition
but
for example the fact that the sum of the
angles of a triangle is 180 degrees
is proved convincingly
um and it comes as a surprise that that
can be done
why is that surprising the the
well it is a surprising uh is a
surprising idea
i suppose uh why is that proved
difficult it's not
that's the point it's so easy and yet
it's so convincing
do you remember what is the proof that
it's um
as up to 180 uh you you
start at a corner and draw
a line um
parallel to the opposite side
and that line sort of trisects the angle
between the other two sides
and uh you you get a
uh a half plane which has to add up to
180 degrees
and it consists in the angles by
by the equality of uh alternate
angles what's it called
you you you get a correspondence between
the angles
created by the side along the side of
the
triangle and the three angles of the
triangle
has geometry had an impact on when you
look into the future of
your work with combinatorial algorithms
has it had some kind of
impact in terms of yeah being able
the puzzles the visual aspects that were
first
so compelling to you not euclidean
geometry
particularly i think
i use tools like linear programming and
integer programming a lot and
but those require
high dimensional visualization and so i
tend to go by the
algebraic properties um right the
you you go by the algebra the linear
algebra and not by the
the visualization well the
interpretation in terms of
for example finding the highest point on
a polyhedron
as in linear programming
is motivating but again
it i don't have the high dimensional
intuition
that would particularly inform me so i
sort of deep lean on the algebra
so to linger on that point what kind of
visualization
do you like do you do when you're trying
to think about
we'll get to combinatorial algorithms
but just algorithms in general
yeah what kind of what what's inside
your mind when you're thinking about
designing algorithms
or or even just tackling any any
mathematical problem
well i think that usually an algorithm
is uh involves a repetition of some
inner loop and
and so i can sort of visualize the um
the distance from the desired solution
as iteratively reducing until you
finally hit the exact solution and try
to take steps that get you closer to the
try to
take steps that get closer and having
the certainty of
converging so it's it's racist
it's basically the mechanics of the
algorithm is often very simple
but especially when you're trying
something out on the computer so for
example
i did some work on the traveling
salesman problem and
i could see there was a particular
function that had to be
minimized and it was fascinating to see
the successive approaches to the minimum
to the optimum
you mean so first of all traveling
salesman problems where you have to
visit
uh every city without ever
the only ones yeah that's right find the
shortest path through
cities yeah uh which is sort of a
canonical standard a really nice problem
that's really hard
right exactly so can you say again
what was nice about the objective being
able to think about the objective
function there and
maximizing it or minimizing it well just
that the um as the algorithm proceeded
it was you were making progress
continual progress
and and eventually getting to the
optimum point
so there's two two parts maybe
maybe you can correct me but first is
like getting an intuition about what the
solution would look like
and or even maybe coming up with a
solution and two is proving that this
thing is
actually going to be pretty good uh what
part is harder for you where's the magic
happen
is it in the first sets of intuitions or
is it
in the detail the messy details of
actually showing
that it is going to get to the exact
solution
and it's going to run at this
at a certain complexity
well the magic is just the fact that it
the the gap from the optimum
decreases monotonically and you can see
it happening
and um various metrics of
what's going on are improving all along
until finally hit the optimum perhaps
later we'll talk about the assignment
problem and i can
illustrate illustrate a little better
yeah now zooming out again
as you write don knuth has called
attention to a breed of people
who derive great aesthetic
pleasure from contemplating the
structure of computational processes
so don calls these folks geeks and you
write that you remember the moment you
realized you were such a person
you were shown the hungarian algorithm
to solve the assignment problem
right so perhaps you can explain what
the assignment problem is and what
uh the hungarian algorithm is
so in the assignment problem you have uh
n boys and in girls and
you are given the desirability
of uh or the cost of matching
the i boy with the jth girl for all i
and j
you're given a matrix of numbers
and you want to find the
one-to-one matching of the boys with the
girls
such that the some of the associated
costs will be
minimized so the the best way
to match the boys with the girls or men
with jobs or any
two sets um no any possible matching is
possible
or yeah all one-to-one correspondences
are
permissible if there is a connection
that is not allowed
then you can think of it as having an
infinite cost
so um what you do is
uh to depend on
the observation that
the identity of the optimal
assignment or as we call it the optimal
permutation
um is not changed if you subtract
a constant from any row or column of the
matrix
you can see that the comparison between
the different assignments is not changed
by that
um because you're penal if you decrease
a particular row
all the elements of a row by some
constant
all solutions decrease by the cost of
that
by an amount equal to that constant
so the idea of the algorithm is to start
with a matrix of
non-negative numbers and
keep subtracting from rows or from
our entire columns um
in such a way that you subtract the same
constant from all the elements of that
row or column
uh while maintaining the property that
um uh
all the elements are non-negative
simple yeah and so and so
um what you have to do
is uh is find
small moves which will decrease the
total cost
while subtracting constants from rows
or columns and there's a particular way
of doing that by computing a kind of
shortest path through the elements in
the matrix
and you just keep going in this way
until you finally get a full permutation
of zeros while the matrix is
non-negative and then you know that that
has to be the cheapest
is that as simple as it sounds
so the the shortest path of the matrix
part
yeah the simplicity lies in how you find
the what i oversimplified slightly what
you
you you will end up subtracting a
constant from some rows
or columns and adding the same constant
back to other rows and columns
so as not to not to reduce any of the
zero
elements you leave them unchanged
but
each individual step modifies us
several rows and columns by the same
amount but
overall decreases the cost so there's
something about
that elegance that made you go aha this
is a beautiful
like it's it's uh it's amazing that
something like this
something so simple can solve a problem
like this yeah it's really cool
if i had mechanical ability i would
probably like to do
woodworking or other activities where
you sort of
shape something in into something
beautiful and orderly and there's
something about the orderly
systematic nature of uh
that innovative algorithm that is
pleasing to me
so what do you think about this idea of
geeks as don knuth calls them
what do you think of is it something uh
specific
to a mindset that allows you to discover
the elegance and
computational processes or is this all
of us can all of us discover this beauty
are you born this way
i think so i always like to play with
numbers i i
i used to amuse myself by multiplying
four digit
decimal numbers in my head and
putting myself to sleep by starting with
one and
doubling the number as long as i could
go and uh
testing my memory my ability to retain
the information
and i also read somewhere that you uh
you wrote
that you enjoyed uh showing off to your
friends
by i believe multiplying four digit
numbers
uh right a couple of four digit numbers
yeah i had a summer job at a beach
resort outside of boston
and uh the other employee i
i was the barker at a skee-ball game
yeah i used to i used to sit at a
microph
microphone saying come one come all come
in and play ski ball
five cents to play nickel to win and so
on that's what a barker i was gonna
i wasn't sure if i should know but
barker that's so you're the
the charming outgoing person is getting
people to uh come in
yeah well i wasn't particularly charming
but i could be very
repetitious and loud and
the other employees were
sort of juvenile delinquents who had no
academic bent but somehow
i found that i could impress them by
by performing this mental melter or
mental arithmetic
you know there's something too that you
know one of
some of the most popular videos on the
internet
is uh there's a there's a youtube
channel called number file that shows
off different mathematical ideas
there's still something really
profoundly interesting to people
about math the the beauty of it
something
even if they don't understand the basic
concept
even being discussed there's something
compelling to it what do you think that
is
any lessons you drew from the early teen
years when you were
showing off to your friends with the
numbers
like is what is it that attracts us to
the beauty of mathematics do you think
the general population not just
the the computer scientists and math the
magicians
i think that it you know you can do
amazing things you can
test whether large numbers are prime
you can uh um
you can solve little puzzles about
cannibals and missionaries
and there's a kind of achievement it's
it's it's
puzzle solving and at a higher level the
fact that you can
you can do this reasoning that you can
prove in an
absolutely ironclad way that the some of
the
angles of a triangle is 180 degrees
yeah it's a nice escape from the
messiness of the real world
where nothing can be proved so and we'll
talk about it but
sometimes the ability to map the real
world into such problems where you can't
prove it is this a is a powerful step
yeah it's amazing that we can do this
another attribute of geeks is they
they're not necessarily uh endowed with
emotional intelligence
so they can live in a world of
abstractions without having to
uh master the complexities of uh dealing
with people
so just to link on the historical note
as a phd student in 1955
he joined the computational lab at
harvard where
howard aiken had built the mark 1 and
the mark iv computers
just to take a step back into that
history what were those computers like
uh the mark iv filled
me a large room much big much bigger
than this large office that we were
talking in now and you could walk around
inside it
they were they were rows of
relays you could just walk around the
interior
and uh the
machine would sometimes fail because of
bugs which literally meant flying
creatures landing on the switches
so i never i never used that machine for
any
practical purpose the
lab eventually acquired a uh
one of one of the earlier um commercial
computers
this is already in the 60s no in the mid
50s in mid 50s
or mid late 50s there was already usual
computers in there yeah we had a univac
a 2000
univac with 2000 words of storage
and so you had to work hard to allocate
the memory properly to
also the excess time from one word to
another
depended on the number of
the particular words and so you there
was an
art to sort of arranging the storage
allocation to
make fetching data rapid
were you attracted to this actual
physical world implementation
of mathematics so it's a mathematical
machine that's
actually doing the math physically
no not at all i think i was a
i was attracted to the underlying
algorithms
so but did you draw any inspiration so
could you have imagined like what did
you imagine was the future of these
giant computers could you imagine that
60 years later would have billions of
these computers
all over the world i couldn't imagine
that
but there was a sense in the
laboratory that this was the wave of the
future
in fact my mother influenced me she she
told me that
data processing was going to be really
big and i should get into it
she's a smart woman yeah she was a smart
woman
and there was just a feeling that
this was going to change the world but i
i didn't think of it in terms of
personal computing i hadn't that
i had no anticipation that we would be
walking around with computers in our
pockets or anything like that
did you see computers as
tools as mathematical mechanisms to
analyze sort of
sort of theoretical computer science or
as the ai folks which is an entire
other community of dreamers yeah that's
something that could
one day have human level intelligence
well ai wasn't very
much on my radar i did read uh turing's
paper about the uh the uh
the uh the drawing test computing and
intelligence
yeah the turing test um what'd you think
about that paper was that just like
science fiction
um i thought that it wasn't a very good
test because it was too subjective so i
i didn't
feel that i didn't feel that the turing
test was really the right way to
calibrate how intelligent an algorithm
could be
to linger on that do you think it's pos
because you've come up with some
incredible
tests later on tests on algorithms right
yeah that are
like strong reliable robust across a
bunch of different classes of algorithms
but returning to this emotional
mess that is intelligence do you think
it's possible
to come up with the test that's as
iron-clad as
some of the computational complexity
work
well i think the greater question is
whether it's possible to achieve
human level level intelligence
right so that's so first of all let me
at the philosophical level do you think
it's possible to create algorithms
that reason and
would seem to us to have the same kind
of intelligence as human beings
it's an open question um it seems to me
that um most of the achievements have
acquire operate within a very limited
set of ground rules and for a very
limited precise task
which is a quite different situation
from the
processes that go on in the minds of
humans which
where they have to sort of function in
changing environments
they have emotions they have
[Music]
um
physical attributes for acquire for
exploring their environment
um they have intuition they have desires
um emotions and
i don't see anything in the current
achievements of what's called
ai that come close to that capability i
don't think there's any
computer program which
surpasses a six-month-old child in terms
of
comprehension of the world
do you think this complexity of human
intelligence
all the cognitive abilities we have all
the emotion
do you think that could be reduced one
day or just
fundamentally can it be reduced to an
out a set of algorithms or an algorithm
so can a touring machine achieve human
level intelligence
i am doubtful about that i guess the
argument
in favor of it is that the human brain
seems to achieve
what we call intelligence cognitive
abilities of different kinds
and if you buy the premise that the
human brain is
just an enormous interconnected set of
switches so to speak
then in principle you should be able to
diagnose what that interconnection
structure is like
characterize the individual switches and
build a
simulation outside but
why that may be true in principle that
cannot be the way we're
eventually going to tackle this problem
it's
you know you know that that does not
seem like a feasible way to go about it
so it there is however an existence
proof that
um uh if you believe that the brain is
is just a network of
of neurons operating by rules i guess
you could say that that's an existence
proof of the ability to build
the capabilities of a mechanism um
but it would be almost impossible to
acquire the information unless we got
enough insight into the operation of the
brain but there's so much mystery there
do you think what do you make of
consciousness for example
there's something as an example of
something we completely have no clue
about
the fact that we have this subjective
experience right is it possible that
this
network of uh this circuit of switches
is able to create something like
consciousness to know its own identity
yeah to know to know the algorithm to
know itself
to know itself i think if you try to
define that
rigorously you'd have a lot of trouble
yeah that's interesting
so i know that there are
many who um
believe that general
intelligence can be achieved and there
are even some who are
feel certain that uh
the singularity will come and uh we will
be surpassed by the machines which will
then
learn more and more about themselves and
reduce humans to an inferior breed
i am doubtful that this will ever be
achieved
just for the fun of it could you linger
on why
what's your intuition why you're
doubtful so there are
quite a few people that are extremely
worried about this
uh existential threat of artificial
intelligence of us being
left behind by the super intelligent
new species what's your intuition why
that's not quite
likely just because
none of the achievements in speech
or robotics or
natural language processing or creation
of
flexible computer assistance or any of
that comes
anywhere near close to
that level of cognition
what do you think about ideas as a sort
of uh if we look at moore's law
and exponential improvement uh to allow
us to
that would surprise us sort of our
intuition fall apart with with
exponential improvement
because i mean we're not able to kind of
we kind of think in linear improvement
yeah we're not able to imagine a world
that goes from the
mark one computer to a an iphone 10.
yeah so do you think it would be we
could be really surprised
by the exponential growth or
or on the flip side is is it possible
that also intelligence is
actually way way way way harder
even with exponential improvement to be
able to crack
i don't think any constant factor
improvement
could could change things and given
given our current comprehension
of how the of
of what cognition requires it seems to
me that
multiplying the speed of the switches by
a factor of a thousand or a million
uh will not be useful until we really
understand the organizational principle
behind the network of switches
well let's jump into the network of
switches and talk about combinatorial
algorithms if we could
let's step back with the very basics
what are combinatorial algorithms
and what are some major examples of
problems they aim to solve a
combinatorial algorithm
is is one which
deals with a a
system of discrete objects that can
occupy various states or take on various
values from a discrete set of values
um and need to be arranged or
or selected um in such a way as to
achieve some to minimize some cost
function
or to prove or to prove the existence of
some
combinatorial so an example
would be um coloring the vertices of a
graph
what's a graph let's step back so what
uh
and it's fun to uh to ask
one of the greatest computer scientists
of all time the most basic questions in
the beginning of most books
but for people who might not know but in
general how you think about it what is
what is a graph
uh a graph that's that's simple it's a
set of points
certain pairs of which are joined by
lines
called edges and they
sort of represent the in different
applications represent the
interconnections between
discrete objects so they could be the
interactions interconnections between
switches
in a digital circuit or
interconnections indicating the
communication patterns of a human
community
um and they could be directed or
undirected and then as you've mentioned
before
might have costs right they can be
directed or undirected
they can be you can think of them as if
if you think if a graph were
representing a
communication network then the edge
could be undirected meaning that
information could flow along it in both
directions
or it could be directed with only
one-way communication
a road system is another example of a
graph with weights
on the edges and then a lot of problems
of optimizing
the efficiency of such networks or
learning about the performance of such
networks
um uh are the
the objective combinatorial algorithm so
it could be
scheduling classes at a school where
the the
vertices the nodes of the network are
the individual
classes and uh the edges indicate the
constraints which say that certain
classes cannot take place at the same
time or
certain teachers are available only at
cert for certain classes
etc or um
i talked earlier about the assignment
problem of matching the boys with the
girls
um where um
you have a very graph with an edge from
each boy to each girl
with a weight indicating the cost
or in logical design of computers
you might want to find a
set of so-called gates switches
that perform logical functions which can
be interconnected to realize some
function
so you you might ask um
how many gates do you need in order to
um
for for a circuit to
give a yes output if at least
a given number of its inputs are ones
and no if not a few are
are present my favorite is probably
all the all the work with network flows
so anytime you have
uh i don't know why it's so compelling
but there's something just beautiful
about it it seems like there's so many
applications and communication networks
in uh traffic right flow
that you can map into these and then you
can think of pipes
and water going through pipes and you
could optimize it in different ways
there's something
always visually and intellectually
compelling to me about it and of course
you've done work there
yeah yeah so so there
the edges represent channels along which
some commodity can flow it might be
gas it might be water it might be
information
maybe supply chain as well like products
being products flowing from one
operation to another
and the edges have a capacity which is
the rate at which the commodity can flow
and a central problem is to
determine given a network of these
channels in this case the edges are
communication channels
the the challenge is to find the maximum
rate
at which the information can flow along
these channels to get from
a source to a destination and
that's a that's a fundamental
combinatorial problem that i i've worked
on
jointly with the scientist jack edmunds
we
i think we're the first to give a formal
proof that
this maximum flow problem through a
network
can be solved in polynomial time
which uh i remember the first time i
learned that
just learning that in um
maybe even grad school i don't think it
was even undergrad no
algorithm yeah do netfl network flows
get taught in in um basic algorithms
courses
yes probably okay so yeah i've i
remember being very surprised that max
flow
is a polynomial time algorithm yeah that
there's a nice fast algorithm that
solves max flow
but so there is an algorithm
named after you an admins they haven't
carp algorithm for max flow so
what was it like tackling that problem
and trying to arrive at a polynomial
time solution
and maybe you can describe the algorithm
maybe you can describe what's the
running time complexity
that you showed yeah well
first of all what is a polynomial time
algorithm yeah perhaps we could
discuss that so yeah let's let's
actually just even
yeah that's what is algorithmic
algorithmic complexity what are the
major
classes of algorithm complexity
so we in in a problem like the
assignment problem
or scheduling schools or
any of these applications um
you have a set of input data
which might for example be um
a set of vertices connected by edges
with
being you're given for each edge the
capacity of the edge
and you have algorithms
which are think of them as computer
programs with operations such as
addition subtraction
multiplication division comparison of
numbers and so on
and you're trying to construct an
algorithm
based on those operations
which will determine in a minimum number
of
computational steps the answer to the
problem in this case the computational
step
is one of those operations and the
answer to the problem
is let's say the um
the configuration of the network that
carries the maximum amount of flow
and an algorithm is said to run in
polynomial time
if as a function of the size of the
input the number of vertices the number
of edges and so on
the number of basic computational steps
grows
only as some fixed power of that size
a linear algorithm would
execute a number of steps linearly
proportional to the size
quadratic algorithm would be steps
proportional to the square of the size
and so on
and algorithms that whose running time
is bounded by some
fixed power of the size are called
polynomial algorithms
and that's supposed to be relatively
fast class of algorithms that's right we
theoreticians take that to be
the definition of an algorithm being
um efficient and and
we're interested in which problems can
be solved by such
efficient algorithms one can argue
whether that's
the right definition of efficient
because you
could have an algorithm whose running
time is the ten thousandth
power of the size of the input and that
wouldn't be
really efficient and in practice it's
oftentimes
reducing from an n squared algorithm to
an n log n or a linear time
is practically the jump that you want to
make
to allow a real world system to solve a
problem
yeah that's also true because especially
as we get very large networks
the size can be in the millions and uh
and then anything above uh
n log n where n is the size would be
uh too much for a practical solution
okay so that's polynomial time
algorithms what other classes of
algorithms are there
what's so that usually they they
designate polynomials of the letter p
yeah there's also
np np complete and be hard yeah
so can you try to disentangle those and
by trying to define them simply
right so a polynomial time algorithm is
one which
was running time is bounded by a
polynomial and the size of the input
uh there's then there's that the class
of such algorithms is
called p in the worst case by the way we
should say
right yeah for every case of the problem
and that's very important that
in this theory when we measure the
complexity of an algorithm
we really measure the
number of step the growth of the number
of steps
in the worst case so you may have an
algorithm that
[Music]
runs very rapidly in most cases but if
there is
any case where it gets into a very long
computation
that would increase the computational
complexity by this measure
and that's a very important issue
because there
as we may have discussed later there are
some very important algorithms which
don't have a good
standing from the point of view of their
worst case performance
and yet are very effective so
so theoreticians are interested in p the
class of problem solvable in polynomial
time
then there's np
which is the class of problems
which may be hard to solve but where the
where when confronted with the solution
you can check it
in polynomial time let me give you an
example there
so if we look at the assignment problem
uh so you have
uh n boys you have n girls you the
number of numbers that
you need to write down to specify the
problem instances
n squared and the question
is
how many steps are needed to solve it
and
jack edmonds and i were the first to
show that it could be done in time
n cubed uh earlier algorithms required
n to the fourth so as a polynomial
function of the size of the input this
is a
fast algorithm now to illustrate the
class
np the question is how long
would it take to verify that a solution
is optimal so for example
if if the input was a graph
we might want to find the largest
clique in the graph or a clique is a set
of vertices
such that any vertex each vertex in the
set is adjacent
to each of the others so the
clique is a complete subgraph
yeah so if it's a facebook social
network everybody's friends
with everybody else it's close click no
that would be what's called a complete
graph it would be
no i mean uh within that click uh within
that clique yeah
yeah they're all friends so a complete
graph is when
everybody is friendly as everybody is
friends with everybody yeah
so the problem might be to determine
whether in a given graph there exists a
clique
of a certain size
well that turns out to be a very hard
problem but how
but if somebody hands you a clique and
asks you to check
whether it is a hands you a set of
vertices and ask you to check whether
it's a clique
you could do that simply by exhaustively
looking at all of the edges between the
vertices and the clique
and verifying that they're all there and
that's a polynomial time
that's a polynomial so the verify there
the problem of finding the clique
appears to be extremely hard but the
problem of verifying a clique
to see if it reaches the target number
of vertices
is easy to solve is easy to verify
so finding the clique is hard checking
it is easy
problems of that nature are called the
non-deterministic polynomial time
algorithms
and that's the class np
and what about mp complete and be hard
okay
let's talk about problems where you're
getting a yes no a yes or no answer
rather than a numerical value so either
there is a
a perfect matching of the of the
boys with the girls or there isn't
it's clear that um every problem in p
is also in np if you can solve the
problem
exactly then you can certainly verify
the solution on the other hand
there are problems in the class np
this is the class of problems that are
easy to check
although they may be hard to solve it's
not at all clear that
problems in np lie in p so for example
if we're
looking at scheduling classes at a
school
the fact that you can
verify when handed a schedule for the
school whether it meets all the
requirements
that doesn't mean that you can find the
schedule rapidly
so intuitively np non-deterministic
polynomial
checking rather than finding
is going to be harder than
is going to include is easier checking
is easier and therefore the class of
problems that can be checked
appears to be much larger than the class
of problems that can be solved
and then you keep adding appears to and
uh sort of these uh additional words
that designate that we don't know for
sure yet
we don't know for sure so the
theoretical question which is considered
to be the most central problem in
theoretical computer science or at least
computational complexity theory
combinatorial algorithm theory
the question is whether p is equal to np
if p were equal to np it would be
amazing it would mean
that every
problem where a solution can be rapidly
checked can actually be solved in
polynomial time we don't really believe
that's true
if you're scheduling classes at a school
it's we expect that if somebody hands
you
a satisfying schedule you can verify
that it works
that doesn't mean that you should be
able to find such a schedule
so intuitively np encompasses a lot more
problems than p so can
we take a small tangent and break apart
that intuition
so do you first of all think that
the biggest sort of open problem in
computer science maybe mathematics
is whether p equals np do you think
p equals np or do you think p
is not equal to np if you had to bet all
your money on it
i would bet that p is unequal to np
uh simply because there are problems
that have been around for centuries and
have been studied intensively in
mathematics
and even more so in the last 50 years
since the
p versus np was stated and
no polynomial time algorithms have been
found for these
easy to check problems so one
one example is a problem that goes back
to the mathematician
gauss who is interested in um
factoring large numbers so uh
we know what a number is prime if it
doesn't
if it cannot be written as the product
of
two or more numbers unequal to one
uh so if we can factor the a number like
91 that's 7 times 13
but if i give you
20 digit or 30 digit numbers you're
probably going to be at a loss to
have any idea whether they can be
factored
so the pr the problem of factoring very
large numbers
is does not appear to have an efficient
solution
but once you have found the factors
express the number as a product the two
smaller numbers you can quickly verify
that they are factors of the number
and your intuition is a lot of people
finding you know this
a lot of brilliant people have tried to
find algorithms for this one particular
problem there's
many others like it that are really well
studied and it would be great
to find an efficient algorithm for right
and in fact we have
some results that i was instrumental in
obtaining
following up on work by the
mathematician stephen cook
to show that within the class
np of easy to check problems
there's a huge number that are
equivalent in the sense that either
all of them or none of them lie in p
and this happens only if p is equal to
np
so if p is unequal to np we would also
know
that
virtually all the standard combinatorial
problems
if p is unequal to np none of them can
be solved in polynomial time
can you explain how that's possible to
tie together so many problems
in a nice bunch that if one is proven to
be efficient
then all are the first
and most important stage of progress was
a result by stephen cook
who showed that a certain problem called
the satisfiability problem
of propositional logic
is as hard as any problem in the class p
so the propositional logic problem
is expressed in terms of
expressions involving the logical
operations
and or and not offering operating
operating on variables that can be
either true or false
so an instance of the problem would be
some formula involving and or and not
and the question would be whether there
is an assignment of
truth values to the variables in the
problem
that would make the formula true so for
example if i take
the formula a or b and a or not b
and not a or b and not a
or not b and take the conjunction of all
four of those
so-called expressions you can determine
that
no assignment of truth values to the
variables a and b
will allow that conjunction of
cl what are called clauses uh to be true
so that's an example of a formula
in propositional logic
involving expressions based on the
operations and
or and not um that's an example of a
problem which has which is not
satisfiable there is no solution that
satisfies all of those constraints
and that's like one of the cleanest and
fundamental problems in computer science
it's like a nice statement of a really
hard problem it's a nice statement a
really hard problem
and and what cook showed is that
every problem in np
is can be re-expressed as
an instance of the satisfiability
problem
so to do that
he used the observation that a very
simple abstract machine called the
turing machine
can be used to describe
any algorithm
an algorithm for any realistic computer
can be translated
into an equivalent algorithm
on one of these turing machines which
are extremely simple
it's a tour machine there's a tape and
you can yeah you have to walk along that
data on a tape and you have basic
instructions
a finite list of instructions which say
we
would say if you're reading a particular
symbol on the tape
and you're in a particular state then
you can move to
a different state and change the state
of the number that you
or the element that you were looking at
the cell of the tape that you were
looking at
and that was like a metaphor and a
mathematical construct that touring put
together to represent
all possible computation all possible
computation now one of these
so-called turing machines is too simple
to be useful in practice
but for theoretical purposes we can
depend on the
fact that an algorithm for any computer
can be
translated into one that would run on a
turing machine
right and then using that fact
um he could sort of describe
any possible nondeterministic polynomial
time algorithm any pro
any algorithm for a problem in np
could be expressed as a sequence of
moves of the turing machine described in
terms of
reading a symbol on the tape
while you're in a given state and moving
to a new state and leaving behind a new
new symbol and given that
the fact that any non-deterministic
polynomial time algorithm
can be described by a list of such
instructions
you could translate the problem
into the language of the satisfiability
problem
is that amazing to you by the way if you
take yourself back when you were first
thinking about the space of problems is
that
how amazing is that it's astonishing
when you look at cook's proof it's not
too difficult to
sort of figure out why this is
why this is so but the implications are
staggering
it tells us that this of all the
problems in
np all the problems where solutions are
easy to check
they can they can all be rewritten
in terms of the satisfiability problem
yeah it's a in adding so much more
weight to the p equals np
question because all it takes is to show
that one
that's right one algorithm in this class
so the p versus np
can be re-expressed is simply asking
whether the
satisfiability problem of propositional
logic
you'll solve a billion polynomial time
but there's more
uh i i encountered cook's paper
when he published it in a conference in
1971.
yeah so when i saw uh cook's paper and
saw
this uh reduction event of all of each
of the problems in np
by a uniform method to to the
satisfiability problem of propositional
logic
that meant that the satisfiability
problem was a universal combinatorial
problem
and it occurred to me
through experience i had had in trying
to solve other combinatorial problems
that there were many other problems
which
seemed to have that universal structure
and so i began looking for
reductions from the satisfiability
to other problems
one of the other problems would be the
so-called integer programming problem
of solving a determining whether there's
a solution to a
um a set of linear inequalities
involving
integer variables just like linear
programming but there's a constraint
that the variables must remain integers
integers in fact must be either zero or
one
because they could only take on those
values and that makes the problem much
harder
yes that makes the problem much harder
and
it was not difficult to show that
the satisfiability problem can be
restated
as an integer programming problem so can
you pause on that was that one of the
first problem
mappings that you try to do and how hard
is that map you said it wasn't hard to
show but
you know that's a that's a big
leap it is a big leap yeah
well let me let me give you another
example um
another problem in np is whether a graph
contains a clique of a given size
and now the question is can we reduce
the propositional
logic problem to the problem
of whether there's a clique of a certain
size
well if you look at the propositional
logic problem it can be expressed as a
number of
clauses each of which is
a
of the form a
or b or c where a is either one of the
variables in the problem or the
negation of one of the variables
and the
an instance of the propositional logic
problem
can be rewritten using operations of
boolean logic can be re
rewritten as the conjunction of a set of
clauses
the and of a set of ors where each
clause
is a disjunction an or
of variables or negated variables
so the pro the question of uh
the in the satisfiability problem
is whether those clauses can be
simultaneously
satisfied now to satisfy all those
clauses you have to
find one of the terms in each clause
which is going to be given that which is
going to be true in your truth
assignment
but you can't make the same variable
both true and false
so if you have the variable a
in one clause and you want to
satisfy that clause by making a true you
can't also make
the complement of a true in some other
clause and so the goal is to make every
single clause
true if it's possible to satisfy this
and
the way you make it true is at least one
term in the clause must be
it must be true so
so now we uh to convert this problem
to something called the independent set
problem where you're
just sort of asking for a set of
vertices in a graph such that no two of
them are adjacent sort of the opposite
of the clique problem
so we've seen that we can now
express that as
finding a
set of terms one in each clause
without picking both the variable
and the negation of that variable
because you if the variable is assigned
the truth value
the negated variable has to have the
opposite truth value
right and so we can construct the graph
where the vertices are the
terms in all of the clauses
and you have an edge
between two
terms if um
if an edge between
two occurrences of terms
if they're both in the same clause
because you're only picking one
element from each clause and also
an edge between them if they represent
opposite values of the same variable
because you can't make a variable both
true and false
and so you get a graph where you have
all of these
occurrences of variables you have edges
which which mean that you're not allowed
to choose
both ends of the edge either because
they're in the same clause or they're
con negations of one another all right
and that's uh
first of all sort of to zoom out that's
a really powerful idea that you can take
a graph and connect it to a
logic equation right somehow and do that
mapping for
all possible formulations of a
particular problem on a graph
yeah i mean that that
still is hard for me to believe that
that's possible
that that they're like what do you make
of that
that um there's such a union of
there's such a friendship among all
these problems across
that somehow are akin to combinatorial
uh algorithms that they're all somehow
related
yeah i i know it can be proven yeah but
what do you make of it
that that that's true
well if they just have the same
expressive power
you can take any one of them and
translate it into the terms of the other
you know
the fact that they have the same
expressive power also somehow
means that they can be translatable
right
and what i did in the 1971 paper was to
take
21 fundamental problems
commonly occurring problems of packing
covering matching and so forth
or lying in the class np
and show that the satisfiability problem
can be
re-expressed as any of those that any of
those have the same
expressive proper uh expressive power
so and that was like throwing down the
gauntlet of saying
there's probably many more problems like
this right but that's just saying that
look that
they're all the same they're all the
same but not exactly
yeah yeah they're all the same in terms
of whether they are
um rich enough to express any of the
others
but that doesn't mean that they have the
same computational complexity
but what we can say is that either
all of these problems or none of them
are solvable in polynomial time
yeah so where does np completeness and
np
hard classes well that's just a small
technicality
so when we're talking about decision
problems
that means that the answer is just yes
or no
there is a clique of size 15 or there's
not a clique of size 15.
on the other hand an optimization
problem would be asking
find the largest clique the answer would
not be yes or no it would be
15. so um
so when you're asking for the
when you're putting a valuation on the
different solutions
and you're asking for the one with the
highest valuation that's an optimization
problem
and there's a very close affinity
between the two kinds of problems
but the counterpart of
being the hardest decision problem
the hardest yes no problem the kind of
part of that
uh is is to minimize or maximize
an objective function and so a problem
that's
hardest in the class when viewed in
terms of optimization
those are called np-hard rather than
np-complete and np-complete is for
decision problems and np-complete is for
decision problems so
if somebody shows that p equals np
what do you think that proof will look
like
if you were to put on yourself if it's
possible to show that as a proof
or to demonstrate an algorithm
all i can say is that it will involve
concepts that we do not now have
and approaches that we don't have do you
think those concepts are out there
in terms of inside complexity theory
inside of computational analysis of
algorithms do you think there's concepts
that are totally outside of the box
that we haven't consi