Video summary
Donald Knuth addresses the popular intuition surrounding the P versus NP problem, specifically challenging the notion that if a solution exists for difficult problems, it must be simple enough for someone to eventually discover and write down. He argues that while an algorithm might theoretically exist to solve certain hard problems, such as determining a winner in the game of Hex—a perfect information game with no possibility of a draw—the total number of possible algorithms is so vast that many valid solutions lie beyond human comprehension or current discovery capabilities. In this context, knowing that an efficient solution exists does not guarantee we can find it, highlighting a significant gap between theoretical existence and practical algorithmic construction. To illustrate the complexity of finding these hidden algorithms, Knuth cites Robert Thomason's theorem in graph theory regarding classes closed under taking minors. The theorem proves that for any such family of graphs, there is a finite number of "bad" minor obstructions; if a given graph contains one of these forbidden structures after shrinking edges or deleting them, it does not belong to the class. For planar graphs, this involves checking against just two specific non-planar minors derived from classic problems like connecting utilities without crossing lines. While Robertson and Seymour proved that such finite sets exist for any arbitrary minor-closed family, identifying exactly which obstructions constitute a specific problem remains unknown in many cases, meaning we possess polynomial-time algorithms based on existence proofs but lack the concrete methods to execute them efficiently. Knuth uses this distinction between knowing an algorithm exists versus actually possessing it as evidence that P might equal NP without leading directly to practical solutions for all hard problems. He points out that there are countless ways to construct valid algorithms, such as representing graphs via prime numbers and performing bitwise operations in polynomial time, which could coincidentally solve specific complex tasks like finding Hamiltonian paths. This abundance of potential algorithmic structures suggests that the sheer volume of possibilities means we must rule out an infinite number of non-working approaches before confirming a solution, yet even with rigorous mathematical proof guaranteeing existence, humanity may never identify the correct one due to its incomprehensible complexity. Finally, Knuth reflects on why he maintains his intuition regarding P equals NP despite decades of effort by brilliant minds failing to produce such algorithms or prove inequality. He compares this situation to the search for extraterrestrial life: just because we have not yet found aliens does not mean they do not exist; similarly, the failure of current researchers might simply indicate that our methods are insufficient rather than proving no solution exists. The possibility remains that a machine learning approach or some other unforeseen mechanism could eventually uncover these solutions, even if traditional human ingenuity has thus far stumbled upon them only to find themselves unable to construct the necessary algorithms within reasonable timeframes.
Read the full video transcript
you've mentioned over the past few years
that you believe P may be equal to NP
but that it's not really you know if
somebody does prove that P equals NP it
will not directly lead to an actual
algorithm to solve difficult problems
can you explain your intuition here has
it been changed and in general on the
difference between easy and difficult
problems of P and NP and so on yes so
the the popular idea is if an algorithm
exists then somebody will find it and
it's just a matter of writing it down
one point what but many more algorithms
exist that anybody can end understand or
ever make your discovery yeah because
they're just way beyond human
comprehension the total number of
algorithms is more than mind-boggling so
so we have situations now where we know
that algorithm exists but we don't know
we don't the foggiest idea what the
algorithms are there's there are simple
examples based on on game playing where
you have no where you say well there
must be an algorithm that exists to win
in the game of hex because for the first
player to win in the game of hex because
hex is always either an L win for the
first player of the second player but
what's the game of hacks there's a game
of hex which is which based on putting
pebbles onto a hexagonal board and and
the white player tries to get a pit path
from left to right and the black player
tries to get a black path from bottom to
top and how does capture occur just so
and there's no capture you just put
pebbles down what one at a time but
there's no draws because they after all
the white and black are played there's
either going to be a white path across
from each to west or a black path from
from bottom to top so there's always you
know it's the perfect information game
and people people click take turns like
like tic-tac-toe
and an export can be different sizes but
we there's no possibility of a draw and
player to move one at a time and so it's
got to be either a first player win or a
second player win mathematically you
follow out all the trees and and either
there's always a win to the four player
second player
okay and it's finite the game is finite
so there's an algorithm that will decide
you can show it has to be one or the
other because the second player could
mimic the first player with kind of a
pairing strategy and so you can show
that it has to be what it has to be one
or that but we don't know any algorithm
no way there there are cases where you
can prove the existence of the solution
but we but nobody knows any way how to
find it but more like the algorithm
question there's a very powerful theorem
and graph theory by Robinson to see more
that says that every class of graphs
that is closed under taking minors has a
has a polynomial time algorithm to
determine whether it's in this class or
not now a class of grass for example
planar graphs these are graphs that you
can draw in a plane without crossing
lines and and the planar graph is closed
taking minors means that you can shrink
an edge in into a point or you can
delete an edge and so you start with a
planar graph and shrinking the edge to a
point is still planar deleting edge is
still planar okay now but there are
millions of different ways to describe a
family of graph that still is remains
the same undertaking minor and Robertson
to Seymour proved that any such family
of graph there is a finite number of
minimum graphs that are
obstructions so that if it's not in the
family then then it has to contain then
there has to be a way to shrink it down
and until you get one of these bad
minimum grafts that's not in the family
for in plate case we're planar graph the
minimum graph is a is a five pointed
star where they're everything pointing
to another and minimum graph consisting
of trying to connect three utilities to
three houses without crossing lines and
so there are two there are two bad
graphs that are not planar and every
every non planar graph contains one of
these two bad graphs by by shrinking and
he said again so he proved that there's
a finite number of these bad guys always
a finite know somebody says here's a
family it's hard to believe and they
present it's sequence of twenty papers I
mean in there it's deep work but it you
know it's because that's for any
arbitrary class so it's for any
arbitrary class that's closed under
taking minors that's closed under maybe
I'm not understanding because it seems
like a lot of them are closed
taking minors almost all the important
classes of graphs are there are tons of
of such graphs but also hundreds of them
that arise in applications like I have a
book over here called classes of graphs
and then and and it it's amazing how
many different classes perhaps people
have looked at so why do you bring up
this theorem lower this proof so you
know there's lots of algorithms that
that are known for special classes of
graphs for example if I have a certain
if I have a chordal graph then I can
color it efficiently if I have took some
kinds of graphs it'll make a great
Network just various things so like
you'd like to test you somebody gives
you a graph that's always it in this
family of grass if so then I hope then I
can I can go to the library and find an
algorithm that's gonna solve my problem
on that graph okay so we we have that we
want to have a graph that says
number than this is give me a graph I'll
tell you whether it's and whether it's
in this family or not okay and so all I
have to do is test whether or not that
does this given graph have a minor
that's one of the bad ones a minor is is
everything you can get by shrinking and
removing edit and given any minor
there's a polynomial time algorithm
saying I can tell whether this is a
minor of you and there's a finite number
of bad cases so I just tried you know
does it have this bad case by polynomial
time I got the answer does he have this
bad case probably time I got the answer
a total polynomial time and so I've
solved the problem however all we know
is that the number of minors is finite
we don't know what we we might only know
one or two of those minors but we don't
know that if we got if we got 20 of them
we don't know there might be 20 125 that
I mean all we know is that is that it's
finite so here we have a polynomial time
algorithm that we don't know mm-hmm
that's a really great example of what
you worry about or why you think P
equals NP won't be useful but still why
do you hold the intuition that P equals
NP because you have to rule out so many
possible algorithms have been not
working you know you can you can take
the graph and you can represent it as in
terms of certain prime numbers and then
you can multiply those together and then
you can then you can take the bitwise
and and and you know and construct some
certain constant in polynomial time and
then that's you know perfectly valid
algorithm and that there's so many
algorithms of that kind a lot of times
we see random you take data and and and
we get coincidences that that that some
fairly random looking number actually is
because because it it happens to it
happens to self it happens to solve a
problem just because you know there's
there's so many hairs on your head
but it seems like unlikely that two
people are going to have the same number
of hairs on their head but but they're
obvious but you can count how many
people there are and how many hairs on
their so there must be people walking
around in the country - I have the same
number of hairs on their head well
that's the kind of a coincidence that
you might say also you know this this
particular combination of operations
just happens to prove that a graph is
has a Hamiltonian path and I see lots of
cases where unexpected things happen
when you have enough enough
possibilities but because the space of
possibility is so huge you have to rule
them all out and so that's the reason
for my intuition is by no means approve
I mean some people say you know well P
can't equal NP because you've had all
these smart people you know the smartest
desire algorithms have been racking
their brains for years and years and and
there's million-dollar prizes out there
and you know none of them nobody has
thought of the algorithm so it must must
be no such job on the other hand I
cannot use exactly the same logic and I
can say well P must be equal to NP
because there's so many smart people out
here been trying to prove it unequal NP
and they've all failed you know this
kind of reminds me of the discussion
about the search for aliens that we've
been trying to look for them and we
haven't found them yet therefore they
don't exist yeah but you can show that
there's so many planets out there that
they very possibly could exist yeah and
right and then there's also the
possibility that that they exist but
they they all discovered machine
learning or something and and and then
blew each other up
you