P vs NP on TV - Computerphile

Our thanks to them.
P vs NP in The Simpsons and Futurama. Featuring author Simon Singh.

Clarification: NP actually stands for non-deterministic (or nondeterministic) polynomial. Simon did us a favour by speaking off-the-cuff on this topic and it is our fault for not cleaning up things in the edit. However Simon's (excellent) book covers this in more detail (pages 157-159 in hard cover) and, in it, he opts for nondeterministic without the hyphen.

Film by Sean Riley and Brady Haran.

[nenicul]

I know an NP-Complete joke, but once you've heard one you've heard them all.

[phrygianphreak]

Computer scientist here!
Okay, so they are kind of on the right track with P-NP, and actually gave a clearer, more accurate statement but it was fragmented throughout the video.
Let's take a simple question that pops up very often in the real world: lets say I have a sheet of cloth, and I have a set of stencils that will punch out shapes to make shirts. Seems easy enough: just arrange the stencils so they don't overlap. That is a P problem. Now here is where the "hard" part comes in: I want you to find the most efficient way of punching out those shapes that is mathematically possible. Then the question becomes difficult for a sequential machine like a computer. We humans may be able to cleverly notice patterns, but computers have no such luxury (yet!). The computer's solution is to essentially try every arrangement possible until it finds the most efficient, because, unfortunately, there is no mathematical way of finding the most efficient arrangement. However, that example is actually known as NP-Hard, because NP problems have the property that if you claim to know the answer, it can be easily checked. What makes this problem one step higher, or NPH, is that one cannot give an arrangement that the computer can easily check. The factoring question he mentioned (what are the factors of a 100 digit number) is truly NP because one can check if the given factors equal that number very easily.
Now onto what "hard to solve" means. The time a certain process takes is incredibly important to computer efficiency.  A problem is difficult if it takes a long time to solve, while easy ones can be solved quickly.
What "Polynomial" and "non-deterministic polynomial" mean is simply whether the time to solve the question is something like x^3 (P) or x^n (NP). As you can tell, the polynomial in P problems is a constant for that question; it's always 3 or 4 or some other real number. NP problems, however, have changing polynomials as in the x^n example, making it non-deterministic aka variable. Just looking at small numbers, something like 3^3 to 4^3 is a difference of 37, while 3^3 to 3^4 is a difference of 54. NP problems' time to solve get long very quickly. 
The reason most CS-s believe P =/= NP is because of something called NP-complete. NP-complete questions are those that if we find a way to get one into polynomial time, whether it be through a trick or new math, then ALL NP problems can be reduced to P. The whole punching out shapes is considered NPC. The reason NPC problems are the core of this question is because every single NPC problem you can conceive can be reduced to this type of question. It's known as a traveling salesman problem, where one is trying to find the most efficient set of decisions. All NPC problems are, at their core, a traveling salesman problem, and just for lay-man's, it is the question of given a salesman is traveling around a state and wants to hit every city only once, what is the most efficient path. This is one of those famous million dollar questions, which some university offering one million dollars for the proof that P=NP. Any time one sees a million dollar reward for a question, realize that it is essentially that scientific community saying, "Yeah, we're pretty sure this isn't true; we can't prove it, but given the hints and evidence we have, we're willing to bet one million dollars that nobody will prove this true." It also doubles as an incentive and motivation to get young researchers to constantly attack the problem in hopes of fame/glory/money/babes etc just in case, because you never know. I know some researchers who would try to disprove gravity if there was a big enough reward out there ;) . 

EDIT:
I've seen a lot of mean-spirited comments on this video. I've seen things like, "THEY GOT IT SO WRONG I'VE LOST ALL MY FAITH IN BRADY, " or, "THIS IS SO WRONG IT MAKES MY HEAD SPIN."
Look, ultimately nothing they said in this video was wrong. Sure, it was fragmented and didn't show the whole problem of P=?=NP, but it really laid a good foundation. 
I'm tired of posters on Numberphile and Computerphile complaining Brady either edits things poorly, or that the people featured have no idea what they are talking about. Yes, this video failed to explain NP-Complete and NP-hard problems, but they gave a good lay-man's explanation that somebody with absolutely no computer knowledge can understand. That's the point: when you are explaining things to people and they have no experience in the field, you have to forgo details so they can begin to grasp the big picture. What disturbs and disappoints me isn't that Brady didn't capture the whole P/NP problem, but that there are so many posters claiming to be teachers who complain that they have to correct misconceptions caused by this video. That is why so many students fail to understand the big picture: my CS instructor who introduced P/NP to me did it in the "you have to know all the details from the very start" approach and EVERYBODY was lost for weeks. It wasn't until in another class where it was being reviewed and the instructor started with an abstract, less detailed explanation that it clicked, and not just for me but many of my peers. These commentators/instructors on this video act like if we don't cover chapters 1-10 on P/NP in one sitting misconceptions will destroy the world! God forbid we have misconceptions!
Hello! That's your job as a teacher: to clear misconceptions! I don't know about you CS teachers watching these videos and holding a grumpy face the whole time, but I'm personally ecstatic that people are all of a sudden so interested in something like P/NP. I love talking about computer science to people, especially those with no experience. If that means we have to start with a more abstract, less detailed explanation, I'm fine with that. That just means we get to talk about it more :)

[Computerphile]

Does ANYONE read the existing comments before adding their own?
Anyone? :)
>Brady

[Computerphile]

Indeed NP stands for non-deterministic (or nondeterministic) polynomial.

Simon did us a favour by speaking off-the-cuff on this topic and it is our fault for not cleaning up things in the edit. However Simon's (excellent) book covers this in more detail (pages 157-159 in hard cover) and, in it, he opts for nondeterministic without the hyphen.

You can download it from Audible where hyphens don't matter so much!!!!

>Brady

[VarmDild]

Simon Singh's remarks about the position of David Cohen strike me as very odd. At the same time you see the equation P=NP, you see the identity 1782^12 + 1841^12 = 1922^12 which is false (I think there's a Numberphile video about it with Simon Singh even). This makes it more likely that Cohen thinks P DOESN'T equal NP, just as 1782^12 + 1841^12 DOESN'T equal 1922^12. It's like an "impossible universe" Homer enters when he goes 3D.

[TheTigero]

The day P=NP is the day that all modern encryption schemes are broken!

[wreynolds]

The equation in The Simpsons did show up in a different dimension, where there was (apparently) a solution to the Fermat equation for n=12. I don't think David S. Cohen was trying to say that P=NP, I think he was trying to say the exact opposite.

[Computerphile]

This is by no means our last word on P vs NP - rather a fun reference to its appearance on these TV shows (which we sprung on Simon without warning - he was a good sport for chatting about it).
Stay tuned for more P vs NP when we interview more people!
>Brady

[ben]

assume P = NP
divide by P: N = 1
substitute in to the original equation: P = P
yes it does
i rpoved it can i have $10^6 pls

[rachitverma]

I believe, the word "hard"(4:00) in computational complexity theory means whether we have been able to find an algorithm that grows linearly, polynomially or logarithmically rather than an algorithm that grows exponentially to solve the problem.
For example the NP-Complete problem Clique, where mankind has simply been unable to find an algorithm to calculate the largest possible clique for a given graph with N vertices, because all algorithms that have been written to solve this usually grow by a factor of 2^n, which is simply exponential.
I believe at 4:00 a proper substitute for the word "hard" would be intractable.

[MaraK_dialmformara]

I don't think putting "P=NP" next to a near-miss solution for Fermat's Last Theorem implies that the writer believes P=NP. Quite the opposite, in fact.

[trudyandgeorge]

I find it hard to swallow that David Cohen /thinks/ that P=NP just because it shows up in an episode he wrote.... that seems like a huge inference there.

[NicolasTsagarides]

I think what makes a problem categorized as NP is the way that the solution is found.

If the solving procedure involves brute-forcing the answer then it is categorized as NP.
If there is a predefined procedure needed to follow on each part of the problem then it is categorized as P.

[rmdavis]

Trivia for you: David Cohen's middle name starts with an S, he has it listed as "David X Cohen" in credits because the writers guild in America do not allow 2 names to be the same, someone had already taken "David S Cohen" so he just decided to list himself as "David X Cohen" (I think because he liked the letter). 
He explains this in the commentary on one of the Futurama episodes (I forget which one =/)

[samgoodwin]

I think it's incorrect to say that NP solutions are easy to check. Checking a solution to the travelling salesman problem is not straightforward. It is itself the travelling salesman problem.

[chromosundrift]

I think it's worth noting that the P and NP distinction belongs to the algorithm which may be taken to be a solution to a problem as opposed to belonging to the problem itself. Sometimes the distinction is merely semantics as in mathematics, algorithms are "problems". Nevertheless, sometimes "real world" problems have as their only known solution an NP algorithm whereas a P algorithm may be discovered/invented later as a better solution to that same "problem".

[NiKLoT]

"Difficult to find a solution, easy to check" pretty sure this is not correct for all NP problems, for example the longest path problem is NP hard, but even if someone gives you a solution you can't really check if it is correct or not (unless you check all possible solutions, but then you wouldn't need someone to give you the solution in the first place) .

[avatar]

My words are the words of an undergraduate computer scientist (I'm currently taking Intro to Algorithms) attempting to clarify the difference between P and NP more thoroughly than that of this video. I'm trying to see if I have this concept correct in my head, so please please please correct me if I am wrong!

There are problems in computer science (for example, the shortest path in a graph) which are able to be solved in polynomial time. It turns out, that the data structure used in solving the problem in turn has an effect of the order of growth for the problem as well, but all in all, the problem is able to be solved in polynomial time.

The case however, changes when you ask for the most efficient path for all possible paths in the graph (more commonly known as the Traveling Salesman problem). According to my professor, the only way the problem can be solved is through a whopping T(n) order of growth within the set O(n!). << Therefore, the problem is not able to be solved in polynomial time (NP).

[DarkadeTV]

My understanding is: if you can find a polynomial time solution for a problem, then the problem is P, but just because you are unable to find it doesn't mean it's NP.

Problems _may be NP;_ maybe you just haven't found a polynomial time solution that proves that this seemingly NP problem is really P.

Check "Big O notation" if you don't know what polynomial/non polynomial time solution means. 

[momentary_]

The only thing I learned from this video is that NP problems are exponentially harder to do than P problems.