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..
