I haven't really thought about this, so be prepared for some vigorous hand waving.
But my understanding of P, NP is that there are a group of problems which we'll
call "P type" problems: polynomial-time type problems and these are problems
that are relatively easy to solve, and then there is another group of problems
called non-polynomial (NP) and these are really hard to solve, okay?
Factoring is one of them, you know, if I say to you - what are the factors of 15?
You can pretty quickly tell me that was 3 and 5. If i gave you a 10 or 20
or a 100 digit number,
factoring becomes really hard. So NP problems are hard to do
P type -- easy, NP -- hard.
The only nice thing about NP type problems is that if I give you the answer,
you can check it very quickly.
So, if I gave you a hundred digit number you wouldn't be able to
factor it, but if I gave you the two factors
you would very quickly be able to say: "Oh yeah they do multiply together to give this hundred digit number".
So NP -- hard to solve, easy to check.
Now the question is this:
Are NP type problems fundamentally different
to P type problems? Or maybe there's a way that some of the NP-type problems,
if we were smart enough, could become P-type problems, are there shortcuts that we just
don't know about? That is obviously really important for computer scientists
because there are hard problems they're working on
if there are shortcuts that could make them easy that would be a dream.
So NP -- hard, easy to check
P-type -- pretty easy to do and easy to check.
Are they fundamentally different? Are they divided? or are they somehow.. could
NP become P-type if we were smart enough?
Now I'm interested in this because
I've read a book about the Simpsons and in the Simpsons one of their Halloween
episodes "Treehouse of Horror VI", one of the writers, David X. Cohen.
Back then he was known as David S. Cohen. I think he changed his name but that is
David S. Cohen back then. He embedded in one of the episodes the
equation P = NP. Now by saying that P = NP Cohen was saying that he
believed that one day they could become unified.
"Did anyone see the movie Tron?"
Now that's not a popular view: they take polls
of computer scientists and mathematicians and they say: "look do you
think P equals NP or do you think he is definitely not
NP?" and the general consensus is that they are not the same. But David
Cohen in the Simpsons was saying: "well actually I kind of think maybe one day
they will become unified". In "Futurama"
(David X. Cohen kind of created Futurama along with Matt Groening).
It's not him it's another writer Jeff Westbrook who was a Yale professor of
computer science before becoming a Simpsons and Futurama writer and Simpsons
writer. In Futurama there is a scene where Fry and Amy are hiding in a cupboard
and behind them
there are files and books and cans and there are two files and one is labeled P
in one is labeled NP. So I think what Jeff Westbrook is saying is P and NP
are fundamentally different and they're in separate folders and you have
to keep them in separate folders because you can never turn an NP type problem into a
P problem, so in Futurama we get the opposite perspective on the problem
The generally more popular view of the problem. But the astonishing thing is
that it pops up in Futurama in prime-time television as it does with the Simpsons.
<When you say one's hard and one's easy
which is saying, for simplicity, is it black and white or is it a gray thing
like is that a long walk
or depends how fit you are or are they fundamental structural differences?>
It's the way that the problem increases in difficulty with the
kind of numbers involved: so factoring (we talked about factoring) is easy if we
have a two digit number 15 is 3 times 5.
If you have a three digit number 121 was 11 x 11 is a little bit
harder but so.. As the numbers get bigger
my understanding is, and I'm ready for the comments to correct me on this,
the problem increases in difficulty in a non-polynomial way
that's where the NP bit comes in. So it's the way the problem gets harder,
the rate at which it gets harder, is what defines it as a truly difficult problem.
We'd like to thank audible.com
for sponsoring this Computerphile video, and if you'd like to check out a
huge range of audiobooks go to audible.com/computerphile and you can
download one for free.
We would like to recommend Simon's book "The Simpsons and their mathematical secrets".
We think both Computerphiles and Numberphiles would really enjoy that.
So get on to audible.com/computerphile
Download the free book and thanks once
again to them for supporting this Computerphile video.
1/10 + 2/10 does
not quite equal 3/10 because to its mind
it doesn't.
I might be able to do some magic here that will replace 8
bytes in the word "computer" with a 2 byte composite pointer of this sort..