- [Announcer] Thank you to Audible
for making this video possible.
- Hi everyone, Jade here.
Today's video is about a problem
that has often been called the biggest unsolved problem
in computer science, P versus NP.
There's currently a $1 million prize waiting
for the person who solves it.
It can roughly be translated to,
if a problem is easy to check the solution to,
is it also easy to find the solution to?
This question sounds crazy.
Like how could this possibly be?
So in this video,
we're going to see what all the hype is about.
Why it's even a question in the first place
and a whole lot more about the nature of computer science.
We're gonna start
in a somewhat unexpected place by playing a game.
This game is called a Number Scrabble
and it's you versus me.
First, I'll pick one of these numbers, one to nine.
Then you pick a number.
The aim of the game is to pick three numbers
that add up to 15.
Whoever does this first, wins.
If all numbers are picked
and no player has exactly 15, the game is a draw.
Now, how would you go about winning this game?
You could do some trial and error.
Spend some time trying to block me from getting to 15.
Pause the video now
if you'd like to think about it for real.
Let me know what you come up with in the comments below.
But what if we reframe the game?
Instead of lining up the numbers in a line,
let's arrange them in a square.
These numbers are arranged in a very specific order.
Every triplet adds to 15.
Two plus seven plus six is 15.
Six plus five plus four is 15.
Six plus one plus eight is 15.
This is called a magic square where every triplet adds
to the same number.
Now, how would you try to win the game?
It seems more obvious now.
You would try to select three numbers
which make a triplet
and block your opponent from doing the same thing.
Hang on, that sounds oddly familiar.
What other game do we know that has those rules?
Yes, Tic-TAC-Toe, or as we say in Australia,
Noughts and Crosses.
To win, you need to draw three noughts or three crosses
in a row while stopping me from doing that.
When we arrange number Scrabble in a magic square,
we see it's really the same game as Tic-TAC-Toe.
A lot of games can be reduced to the exact same game.
And a lot of problems in math and computer science
can be reduced to the exact same problem.
If two problems can be reduced to the same problem,
they can be solved by the same strategy.
Any strategy that can solve Tic-TAC-Toe
can also solve Number Scrabble.
In math and computer science,
these strategies are called algorithms.
And they're mechanical procedures, kind of like a recipe.
You don't need to think when carrying it out,
just follow each step until you've reached the solution.
Depending on the problem,
algorithms can be more or less complex.
Just like depending on the food,
recipes can be more or less complex.
How complicated an algorithm a problem needs to solve
is one of the main areas of interest in computer science.
It's so important in fact, that problems are grouped
into classes based on how complicated they are.
This area of computer science
is called computational complexity
and the groups of problems are called complexity classes.
Each complexity class has its own name.
And the two we're interested in are P and NP.
Yes, P and NP are just classes of problems
based on how difficult they are to solve.
P is the class of all problems
which have an algorithm that can be computed
in polynomial time.
A polynomial is any number that has a power or exponent
which is also a number like n to the power of two
or n to the power of five.
The n refers to the number of inputs to the problem.
So we can say that the number
of steps the algorithm needs to take is proportional
to the input size.
This makes sense.
If I asked you to sort this list of five numbers
from lowest to highest for $10, you'd probably do it.
But if I asked you to sort this number
of 10,000 numbers for $10,
you'd probably tell me to (indistinct).
Is this because sorting the larger list
takes a lot more steps and so a lot more time?
It's exactly the same for computers,
except that they're are a lot faster than we are
and can solve problems
with a polynomial number of steps pretty quickly.
In other words, the class P refers
to all problems that a computer can solve
in a reasonable amount of time.
NP on the other hand are the class of problems
that can be verified in polynomial time
but may take an exponential number of steps to solve.
An exponential is when the input number n
is in the exponent or the power, like two to the power of n.
Now here's the important difference.
Computers take an extremely long time
to solve these kinds of problems.
To demonstrate the difference
between a P problem and an NP problem,
if a problem is in the class P and has 100 inputs,
and its algorithm is proportional
to n to the power of three, a polynomial,
it'll solve its problem in about three hours.
If it's an NP problem with a completion time proportional
to two to the power of n,
it'll take roughly 300 quintillion years to solve
longer than the age of the universe say.
So yeah, there's a bit of a difference
but although they take a very long time to calculate,
NP problems take a relatively short time to verify.
This is pretty intuitive.
Sudoku is an NP problem.
It takes some effort and time to solve
but once it's solved,
it's pretty quick to check that it's correct.
So now we've finally gotten to the crux of the question.
The question, does P equal NP,
is asking whether these two complexity classes, P and NP,
are in fact the same class?
That is, can we perhaps solve these exponential problems
in polynomial time?
Or framed another way,
are questions that are verified in polynomial time
also solved in polynomial time?
Now it was at this stage in my research
that I found something deeply confusing.
And that is, why is this even a question?
I mean, for something to be called the biggest open problem
in computer science, there needs to be some kind
of ambiguity around the answer.
Like, do we have any reason to believe
that P might equal NP?
I mean, the question is basically asking is this thing
that doesn't look like this other thing, really that thing?
this annoyed me so much
that I spent two whole afternoons googling it.
And I found three things.
One, most computer science research is don't think
that P equals NP, okay.
Two, a somewhat unsatisfying answer
to my question was that, well, it hasn't been proven
that P doesn't equal NP,
but I mean, a lot of things haven't been proven.
It hasn't been proven
that you can't raise people from the dead
and there's no million dollar prize about that.
And three, another common reason I came
across for why this is a question
is that it would improve the world by unimaginable amounts,
if unimaginable amounts, if P did equal NP.
But I mean, lots of things would improve the world a lot.
Like why is this question a question?
At the end of the afternoon,
I did come across what I found to be a reasonable answer.
But before I tell you that,
I'd first like to tell you what would happen
if it turned out that P did equal NP.
Optimization problems like transport rooting,
production of goods, job scheduling,
circuit and database design are all NP problems.
Imagine how much more efficient the economy would be
if we could find the most optimal solutions
to all these problems?
There would be massive advances
in machine learning as problems that are easy to check
would become just as easy to solve.
The problem of protein folding is an NP problem.
If we could solve it, we could cure cancer.
To quote MIT complexity researcher, Scott Aaronson,
"If P were equal to NP,
then the world would be a profoundly different place
than we usually assume it to be.
There would be no special value in creative leaps,
no fundamental gap
between solving a problem and recognizing the solution
once it's found.
Everyone who could appreciate a symphony would be Mozart.
Everyone who could follow a step-by-step argument
would be Gauss.
Everyone who could recognize a good investment strategy
would be Warren Buffet."
And most importantly, we could finally be Candy Crush.
Yes, Candy Crush is one of these NP hard problems.
However, there is a downside to this golden metropolis.
Encryption, the math that keeps your bank details
and privacy safe, relies on P being different to NP.
If P was shown to be equal to NP,
all of your passwords and therefore, all of your information
would be free game for the world.
So apart from you potentially losing your life savings,
it would be pretty cool if P did equal NP.
Being able to solve any problem
just as easy as checking the solution
to that problem would make life insanely easier.
There's no lack of motivation for wanting P to equal NP.
But just because it would be nice,
why does that mean it's a major
and famous problem in computer science?
Well, to understand that first,
imagine this scenario,
your boss asked you to sort this list of numbers.
You fluffed your way through the job interview
and don't know much about coding.
So you write a very simple algorithm.
It goes through an entire array
and compares each neighboring number.
It puts the larger value on the right
and the smaller value on the left.
It continues this process until the array is fully sorted.
The runtime of this algorithm is of the order
of n to the power of two,
which means that if there are 100 inputs,
it will take a maximum of about 10,000 steps.
You're pretty proud of yourself, but your boss isn't happy.
Make a faster one or you're fired.
You've got a family to feed.
You've got to get serious.
You write a new program, which takes an array,
splits it in two down the middle and keeps doing so
until there are only squares of a one left.
It takes two neighboring squares
and sorts them with the lower number on the left
and the higher number on the right.
It then looks at the neighboring pairs
and compares the lower numbers with each other.
Sorts them, then compares the higher numbers and sorts them.
Then combines the array.
It keeps repeating this process,
which in turn,
takes the two arrays and compares the values
of the first number of each array.
Comparing and sorting likes squares
and then combining everything
until finally, we end up with a full array
of sorted numbers.
This new algorithm has a runtime of the order of n log n,
which means that if there are 100 inputs,
it'll take around just 200 steps.
A massive improvement on the 10,000 steps from before,
it looks like you deserve the job after all.
The point of all of this
is that sometimes you can improve an algorithm
so that it solves a problem faster.
The problem didn't change.
You still needed to sort a list of numbers
but by being clever and a bit scared,
you managed to find a faster way to do it.
This is exactly what happened
in the case of some NP problems.
It was deemed that they couldn't be solved
in polynomial time, but then some clever person
came along with an amazing algorithm
and managed to transport the problem from the NP realm
to the cozy comfiness of the P realm.
Now you're probably thinking, wait, Jade, if it was shown
that some NP problems were in fact equal to P,
doesn't that prove that P equals NP?
Well, you would think so, but the answer is no.
Here's where things get a little bit fiddly
but just pay attention and you'll be fine.
So complexity classes aren't like totally separate things.
Some of them are more like Russian dolls
in that they contain other classes.
You'll see that the class of P is actually contained
within NP.
See, not all problems in NP take the same amount
of time to solve,
but rather, they can all be solved
in exponential time or less.
Problems in P can obviously be solved
in exponential time or less.
If you can solve something in less than a 100 years,
you can definitely solve it in less than a 1000 years.
So NP is the class of all problems that can be solved
in exponential time or less.
Now see this, NP complete circle here.
They are the hardest problems in the whole class of NP.
And they take the longest time to solve.
Some problems from the middle of NP were shown to be in P
but none of the NP complete problems ever have been.
So the question, does P equal NP really means,
are NP complete problems the hardest problems in NP
in the class P?
Was that confusing?
I got a bit confused.
Let me say it again.
NP problems can all be solved in exponential time or less.
Some NP problems, those in P,
can be solved in polynomial time or less.
Therefore the class P is contained within NP.
Some NP problems have been shown to be in the class P.
However, the hardest problems in NP, the NP complete ones,
have never been shown to be in the class P.
So the question of whether P equals NP
still isn't solved
because this NP refers to NP complete problems.
And now to return to the original motivation
for this whole bit, why is P equal NP such a big question?
Well, if just one of the NP complete problems
was shown to be in the class P,
that would mean that all of the NP complete problems
would be in the class of P.
Just like solving Number Scrabble also solves Tic-Tac-Toe.
And if some NP problems have been shown to be in P,
it's not too crazy
to think that maybe just one NP complete problem
might be in the class of P.
Maybe some rebel with a totally radical idea
will come up with an amazing algorithm.
If they showed that just one NP problem could be reduced
to a P problem,
this would show that all NP problems could be reduced
to P problems.
And that P does in fact equal NP.
You could be Mozart, Warren Buffet, and Gauss, all in one.
Cancer would be cured.
And you could finally get to work on time.
And most importantly, beat the high score in Candy Crush.
We've seen today that a powerful algorithm has the potential
to change your life for the better
but what powerful algorithms already exist
that you can start using today?
For example, did you know
that there was an algorithm that will tell you
the best strategy to find love?
There's an algorithm that tells you
when the best time to try new things is,
and when to stick to what you know.
Another one to tell you when to reconnect with friends
and when to leave things to chance.
When I first started getting interested
in computer science,
what fascinated me most was the pure logic behind it.
How you can take a very abstract question
like when should you try new things.
And break it down and even come up with an algorithm
to solve it.
One of the first books I read was "Algorithms to Live By"
by Brian Christian and Tom Griffiths.
I'd recommend it to anyone who's interested
in learning about computer science.
It's written in a very nice, conversational tone.
So it's very accessible for beginners.
It gives the overall idea
behind the algorithms without getting too technical.
So yes, I would highly recommend it.
If you are interested in reading this book,
this video's sponsor, Audible,
is offering a free 30 day trial
to anyone who signs up with the link
audible.com/upandatom, or texts upandatom to 500-500.
Your trial includes three free audio books,
including any one title of choosing
and any two audible originals of your choosing.
I started using Audible about a year ago
and parts of my day that used to be a drag
like catching the bus or being stuck in traffic.
I actually now really look forward to.
I can just plug into Audible
and suddenly, I'm listening to Brian Green
reveal the secrets of the universe.
To start your 30 day trial,
just go to audible.com/upandatom
or text upandatom to 500-500.
As always, a huge thank you to all my Patreons
who make these videos possible.
Thank you for watching
and I'll see you in the next episode.
(soft music)