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 :)
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
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.
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
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.
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.
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.
Well, how's it modified? If it's slightly incorrect, then it fits in with the Fermat near-miss and strengthens my case for the writers not believing P=NP.
It's not incorrect, just a rearrangement of numbers. In fact, e^iπ+1=0 and e^πi=-1 are both correct.
10 лет назад+8
In the book "Simpsons and their mathematical secrets", it is stated that Davis S(/X) Cohen is in fact a supporter of P=NP. As I understand it, this is backed by actual interviews.
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.
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!).
"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) .
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.
Just a short of clarification (you may delete this if it was written before... I didn't see it and I really tried to find something that actually explains the classes and defines them): * Decision problems in P (such as Path finding or Prime test (yes it is in P)) are called Deterministic Polynomial Time problems because there exists a Deterministic Turing Machine that can be solve the problem in a polynomial time. * Decision problems in NP are problems that, for a given solution, you could check in a polynomial time if the solution is correct. For instance: Hamiltonian path is in NP because you really have to check all possible paths to see if the graph has a Hamiltonian path in it. However, given a set of nodes and a graph, you can check in a linear time if that set of nodes is a Hamiltonian path (linear is a polynomial of the first (1) degree). So - problems in NP are problems that a solution to them could be verified in a polynomial time. This doesn't explain the NP which is Non-Deterministic Polynomial time. The second definition of NP is the set of all problems that could be solved in a polynomial time on a NON-deterministic Turning machine.
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.
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 =/)
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".
I like the video. I wish he would assume the viewer understood exponents. Most people do if you use the right terminology -- square-footage over your home, number of marbles in a jar, etc. To a layman I would give examples of searching a linear list is is "N" time. Sorting a list is "N squared". Or N to the second power. Second power is a simple number, 2. It could be 3 or 4, and it would remain P. But if the complexity is relative to the size of the problem space, such as "to the N power" for N elements, then it becomes NP. This is actually not a great definition in scientific terms. This is just a property of NP, but that's not what makes it NP. However, it's enough for someone with just some high school Math to grasp the difference.
I'm a software engineer & I've studied this a lot, so I think I can clarify this. P means it can be worked in linear loops, like w/ Bubble Sort, if you have 10 numbers, you compare each of the 10 numbers to each of the other numbers, so it's 10^2 or 100 comparisons. NP is like 10^N, so if N=10, that means 10000000000 comparisons or other operations that must be performed & your computer may crash before you get done :) Are they the same????? Well, what do you mean by that, eh? They are conceptually different; however all of these algorithms are intended to work out some useful task as it relates to the real world (designing a better engine, or maximizing efficiency of your business, etc). We call this "the problem you are working on." Now if you spend enough time studying the fundamental problem you're working on, you can often find a different approach, or an approximation of the original approach that that is P not NP. For example one of my professors found an algorithm that was N^10th power whereas the previous fastest algorithm was exponential (like 10^N). Therefore, mathematically, they are fundamentally different, but you can sometimes use P to approximate NP (like Taylor polynomials in calculus), or you may give up on the approach you've been taking to solve your problem & find a better approach that is P instead of NP.
And BTW, there was a paper while back talking about when they come out w/ Quantum Computers, they will factor large numbers very quickly, which means most of the encryptions on the internet will have to be changed, but many NP problems will stay NP hard - like trying to get a computer to work out mathematical proofs for you - it's a N! problem & Quantum Computers would only speed that up slightly.
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.
I believe this topic belongs to Numberphile more than to Computerphile even though it is about computational complexity. It's a mathematics discipline more than computer science as many P problems are still too impractical for computers. Imagine you have an algorithm which works in N^80. It ends quite fast if N=1, but even for N=2 it suddenly lasts quite a while and for N=100 all the computers in the world will not help you calculate it in time. The matter is, all NP-hard problems are equal. I.e. they can be converted to each other in polynomial time. If a polynomial solution is found for one, it's found for all of them.
I get why you said that shoul be in numerphile, but this is still a computer problem, computer science is not only about computers but also about the theoric aspects of it, so even in this problem is mainly a math problem I belive is still full related to computer, just my thougt.
bnightm I don't know that the thought was original, but I've always heard this attributed to Dijkstra's quote that the name "computer science" is "like referring to surgery as 'knife science'". I think this would be an interesting topic for a more general Computerphile video. When I was doing my degree there was a lot of pressure from certain directions to reduce the volume of mathematics, logic and theory of computation in favour of so-called "practical skills", which seemed to mean learning more industry-favoured programming languages. In my life since I've found that people tend to equate my CS degree with being able to fix their printer or help them send an email. In my view complexity classes and computability lie at the very core of computer science, but I'd love to listen to some of the Computerphile contributors' thoughts on the topic.
The N and P deal with, as I understand, the number of steps or calculations that need to be taken to arrive at a useful solution. The whole premise leaves out the idea of formulating a new and more appropriate algorithm. Let's look at the Chess simulators, or chess player games, because those are a good example. If you want a good example of an uncomputable problem, look at a chess game after five moves. So you need to include the idea that you trim the tree of possible outcomes. This is one way you can attack, computationally, a problem of almost infinite complexity. Same for the travelling salesman problem. It might prove to be almost impossible to calculate all possible alternative solutions to find the single shortest, but you can prune a hell of a lot of possibles out within 3 or 4 moves. Like the boys at Bletchly Park showed with Enigma, you don't brute force the thing, you look for cheats and hints and ways to trim the field of possibles. The trick, the art, is finding a way to do the thing that doesn't expand at N ^ M ^ M .... The trick is to find algorithms that don't 'explode' in progress. Many things seem at first, as if they must. Chess is one good example.
Exactly, like alpha-beta pruning in MiniMax game trees. Or knowing how many zeros there are in 1000! By using cheats and math shortcuts. It is a point where art, science, and out-of-the-box thinking meet.
In simple terms, NP means that the problem is "easy" to check, while P problems are "easy" to check and to compute the answer to. our current understanding of the subject indicates that being "easy" to check is not enough to be "easy" do compute, at least not with a normal computer processor. This is important, since it's the basis on which the convenient kind of cryptography we use everywhere can work at all.
Here's a proper explanation of the P vs. NP problem. The video is, simply, incorrect. We say a problem is "in P" if it can be solved in "polynomial time" - that is, the running time of the solver grows as a polynomial function, not, say, exponential. (That is, the running time t(N) is less than cN^d, for some constants c and d where N is the size of the input to the problem.) We (arbitrarily) say these problems are easy, though of course if c or d are large, they may take a long time to solve. In simple terms, a problem is in P if it has a "fast" solver. Now, suppose I give you a solution to any problem, and asked you to tell me if my solution was correct. You would come up with a "verifier" that checks if my solution is valid. If your verifier itself runs in polynomial time, we say that the problem I solved is in NP. This has the consequence that *any* problem in P is in NP. If I give you a solution, you could simply run the solver algorithm to check if my answer is correct. The P vs NP question is asking whether it is the case that if a problem's solution can be checked easily, the problem can be *solved* easily. Concretely, consider factoring. At present, there is no polynomial time solution for factoring a large number - this problem is hard. However, suppose I gave you two numbers I claim are factors of a larger number. You could check this easily by multiplying my factors together and verifying they do, in fact, produce the original number. Because this verification is easy, we say factoring is in NP. To summarize - All problems in P are in NP. If the reverse is true (all problems in NP are in P) then we have shown that P=NP. The video suggests that P problems are easy and NP problems are hard, but in fact this is not true.
Someone asked "what's the mathematical definition of an NP problem?" The best answer I can give is its a problem where the best known method of solving would take on the order of the age of the universe to work out for some sufficiently large input. All algorithms have an asymptotic running time complexity, that is, the time it would take to solve given some input of size X where X tends to infinity. For example if I want to sum a series of numbers that is X numbers long that would take T=X time (one time unit for each number I want to add). A series 10 numbers long takes 10 time units, 1,000,000 numbers long takes 1,000,000 time units and so on. If you were to graph this out with size of the input on one axis and the time it takes to solve on the other axis you would get a straight line so we say this takes linear time. If I change the the problem slightly and now say I want to sum some series of numbers in a matrix that is X numbers by X numbers in size it will now take T=X*X or T=X^2 time (X time for each row multiplied by X columns). Now if I I plug in X=10 it takes 100 time units to solve and if I plug in 1,000,000 for X it takes 1,000,000,000,000 time units to solve. If we were to graph this function you would get the graph of X^2 which you can see grows much more quickly than the graph of T=X. This means that a solution that runs in X^2 time will take MUCH longer to run when X gets sufficiently large. With NP type problems we don't have running times of X or X^2 which are general considered "pretty good" but more like a^X (where a is some integer) or X! or X^X which grow extremely rapidly and even with "modest" size inputs would take the best supercomputers trillions of years to solve. I'm not sure that there is a hard, fast line in running time complexity where we say "that's an NP problem" but if after doing the math you find out the best known algorithm to solve your problem will take something like the age of the earth to run then chances are you have a candidate NP problem.....or a really crappy algorithm (which brings us back to the whole question does P = NP, is the problem truly unsolvable in any reasonable amount of time or have we just not found the right algorithm to do it?).
Factoring is indeed an NP problem because it has a verifier that runs in polynomial time (simply multiply the two factors together). I think what you mean is that it is not NP-Complete, in which case you are likely (though not certainly!) right.
You are correct I phrased that poorly. What I meant was that factoring is an O(sqrt(n)) problem, and therefore a solution to p vs np would not have an implication for our ability factor numbers quickly.
Actually, this is a common misunderstanding - factoring is not, in fact, O(sqrt(N)). The reason for this is that the size of the input is defined to be the number of bits required to represent it, not the magnitude of the number. The number of bits needed to represent arbitrary N is B = log_2(N). The factoring algorithm you suggest is O(sqrt(N)) - since N=2^B, your algorithm is O(sqrt(2^B)) = O(2^(B/2)) and is therefore exponential, not polynomial.
Correct me if Im wrong but I think the increase in time taken for a program to find all factors of a number N could be less than the proportional increase in N ie for large N t1= f (n) t2=f(2n) t2 < 2t1. My thinking is that first the number of potential primes to check would increase at a slower proportional rate than the size of root N. Bigger than root N don't need to be checked and prime numbers become less frequent the larger you go. Second if N is a factor of 2 larger it only takes 1 more bit to store it so thats not a problem . Third the factor test could be done by approximating a number to multiply by and subtracting the multiple from InI until close enough to run through taking the prime from n until n is 0 or negative. The time to check could increase at a slower proportional rate than the size of N and could be roughly proportional to a log function of N so increase at a rate less than root N. combined for large N you get (less than root N)^2 + log base 2 (N) .
luaudesigndf Shows it can be done. I wouldn't stand a chance solving any of those though the best I could do is run calculations on an int or long in vb and hopefully get a less than linear increase in difficulty as the numbers scale.
I think P=NP is accurate myself, because where would you draw the line between "easy" and "hard" which are both subjective terms. That line moves around for every person. Certainly in his example 15 is much easier for most people to factor, but as you increase the number, who's to say if one person starts moving into NP territory at one point while another continues on for quite a while before it becomes NP for them.
This is the what I read about the P vs NP problem (which probably isn't entirely true): P computational time: ∝ inputs to a number (e.g. inputs^ 5) NP computational time: ∝ a number raised to inputs (e.g. 2^ inputs) This is how I visualized what was written: On a log(time) versus inputs graph, the slope of P problems decrease with time while NP problems form a straight line. On a log(time) versus log(inputs) graph, P problems form a straight line while NP problems curve upward.
For clarity, I think that one should refer to "(N)P-type calculations". If P = NP, then a "hard" problem might have one means of solution that is NP but it also has a solution that is P; it would be a misnomer to label such a problem as being an NP problem, since it is actually a P problem and only a given calculation for it may be NP. If P =/= NP, then the issue does not arise (since all problems that have P solutions are P problems and all problems that have NP solutions also lack P solutions and thus are fundamentally NP problems). But, since the conjecture has not yet been determined, we should make our language deliberately careful.
At the end of the video Mr Singh says that the difficulty of factorization increases as the numbers get bigger. Factorizing a 3 digit number is clearly more difficult than a 2 digit number, but my question is: there is a way to measure the increase in difficulty of a problem? I mean, is there a sort of function for difficulty, which tells us exactly how difficult a problem is?
Oh man, I was so excited when I saw the title of this video and then you come up with a video that explains very little but repeats common misconceptions instead :( I mean if NP were "non-polynomial problems" then the whole "Is P=NP?" debate would be over before it began. Also, it's not "some problems" from NP that might "jump over" to P, it's all or nothing (either P is a subset of NP or it is the same set).
Having never encountered the terms P and NP before, and seeing this first thing in the morning, my brain assumed we'd be talking about transistors.... BRAIN FAIL. But great intro to the subject!
Would it not be less ambiguous to define "solving strategies" as being either P or NP, instead of the problem itself? What I mean is that the difficulty of finding a solution is not necessarily depending on the question (problem), but on the way (strategy) you find the answer (solution). By such a redefinition of P and NP, finding the factors of a number (121=11x11) is only an NP problem when using the current strategies to find the solution, would a strategy (algorithm) be found to solve this in P time, then only the new strategy becomes P, the old strategy is still NP. But the problem has shifted from NP to P, because there is a strategy in P for the problem.
Complexity Theory is a computable extension of the Turing Machine itself. NP vs P is the nonsensical statement by which two logical arguments contradict each other only to balance and imbalance themselves out indefinitely. Its the limitation of the frame in and of itself which makes the technique find its boundary - its the end of boolean logic in the same sense Godel spoke about incompletitudes in formal logic. You want to solve NP vs P you have to kill-off the turing machine and start over again with something else - maybe an Oracle Turing Machine with a diffuse switch which stochastically resets the machine so it can reframe itself with different components until the problem in hand is solvable. This problem will never be solved with the TM.
As problems increase in difficulty, it there a gradual transition from P to Non-P, or a distinct step; or are they fundamentally different in some way?
The example given, Factoring, is not known to be NP-complete. Indeed, it may be in P but there may be other problems that are not. NP-complete problems, such as 3-SAT, are known, such that if 1 can be shown to be in P, then NP=P.
(OK, actually watched the video) He doesn't really say NP-hard or -complete though, he just says NP. As long as there is no P algorithm for it... that's fine. But I guess it's not the typical example one would use.
Actually NP stands for "nondeterministic polynomial". Which means that if you (or a nondeterministic turingmashine) always guess correct, you can solve the problem in polynomial time. So guessing and checking if The guessed solution is correct both are polynomial. And btw, since Simon uses the phrase "NP hard" several times: There is a subtle difference between "NP", "NP hard" and "NP complete".
Thank you for explicating that points. :-) It seems to me that "NP means nonpolynomic" is an easy and widespread misconception. And of course a nondeterministic Turing machine is purly theoretical, but so is a regular Turing machine. ;-) But that's things you have to handle with when talking about complexity and (in my opinion) it's the fascinating insides of that mysterious "NP" everyone talks about. %-) I know this only was meant to be a rough overview and no introduction to complexity theory. I'm sure in *that* video everything will be fine. :-) Robin
It's worth noting that NP does not stand for "Non-Polynomial" but for "Non-deterministic Polynomial." This is because it's the class of problems which can run in polynomial time on a non-deterministic Turing machine.
Yea but for encryption to remain valid once we have better quantum computer we are going to need to switch to EXP based encryption so the machine wont be able to keep up with the complexity
From what I understand, the factoring problem becomes more difficult because keeping track of primes becomes more difficult. It is easy as long as all possible prime factors are known in a list. But once you start dealing with numbers which could be squares (or higher) of primes that you are unaware of, the problem reduces to the problem of finding primes.
P is the set of all problems solvable in polynomial time. NP is the set of all problems with answers that can be checked in polynomial time. If we had a problem A in which all NP problems can be reduced to it (in polynomial time) so that a solution for A will solve them, A is said to be NP-hard. Now if someone ever finds just one problem that is both an NP-hard problem, and a P problem, P = NP
In our world, computers cannot infinitely multiply on each branching step, so they have to simulate each instance of non-deterministic one. And this number is growing exponentially.
P as the class of problems solvable by a deterministic Turing machine in polynomial time. NP as the class of problems solvable by a nondeterministic Turing machine in polynomial time.
P ≠ NP actually means P ⊂ NP, since all P problems are (obviously) in NP. We know perfectly well how to solve "some" of NP problems in polinomial time, we don't know if we can do that for "all" of them. What the video is actually referring to is NP-complete problems, NP problems that we don't know how to solve in P.
Like some of the people in the comments, I got the feeling that I probably know more about P=NP than Simon Singh does, but I still enjoyed this video. It's pretty clearly not a technical overview of computational complexity theory. He was on the money when it comes to the spirit of the topic and even he is clear that he isn't a professional, so no one is being misled.
I had a subject in university called Graph theory and on time we had to write some code to calculate a solution for the "Traveling salesman problem" (find the shortest path for a person so that (s)he visits a certain amount of cities which distances you all know). It was easy for a few cities (something like 6 or 7) but the more you add the harder it gets. You can find an approximate solution but if you want to know the true answer you will have to check all n! possibilities and pick the shortest one (6! = 720, 7! = 5040, 8! = 40320, 9! = 362880). It just gets too hard to quickly. I really like thinking about solving this one day like an easy P problem but until then we have to live with it :)
Indeed NP hard problems might be solvable with an algorithm that does not have a polynomial time solution like e.g. order n^3 but perhaps n exponential time like 2^n, any problem that has an algorithm where the time complexity for solving it (in terms of the size of the input n) is greater than polynomial is said to be NP hard. The group of NP hard problems that can be reduced to each other (i.e., if I can solve one problem I can solve the other by 'massaging' the solution in polynomial time) is said to be the group of NP complete problems.
if you guys are interested in the consequences of N = NP, you should see the videos about security and encryption using multiplication of primes numbers
I was expecting a nod to the show Numb3rs, where the main character sometimes is working on this exact problem in his garage. There is a beautiful episode (can't remember which one) where he is very upset by something and hides in his garage for days on end, just working on P vs NP. In the end he is convinced P vs NP cannot be solved
P (polynomial) problems are problems solved in polynomial time, the traveling salesman problem is a NP (non-polynomial) problem where you don't know how long it takes to solve it, so it's solved in non-polynomial time. The question is, if there is any way to solve the traveling salesman problem in polynomial time, for example an algorithm. The only way of solving the traveling salesman problem currently is to check every possible salesman way and see which is the shortest.
"You can't solve a problem by the same line of thinking that caused it" Einstein The biggest problem of P vs NP is how it is framed. Since solving P vs Np is an "NP problem" there is no mechanism for solving it without the answer. Reframe the thing as an informational problem and figure out how you can frame it in a way where you can use Claude Shannon's informational entropy and it will become solvable. Not easy, but solvable.
so to clarify, is it that a "p" type problem has a low number of factor? ex: 20= 4x5=2x10 and an "np" type problem as many? ex:104,856,007,582,823,786=(a shit ton of combinations of factors)
If you wanna see an amazing and accurate video on this topic, look to your right. You'll probably see (if not, search) a video titled: *P vs. NP and the Computational Complexity Zoo* Just watch it right away, I assure you it will be the best short video you'll watch on this topic.
This is the most fascinating question I've ever come across. I personally think that all problems are inherently as difficult as each other, and it comes down to the tools you're using to solve them. There is no “p vs. np” from the standpoint of infinite toolset, since every problem can be solved in constant time, there's a tool that simply gives you the answer. The real question we're asking with “p=np?” is, granted our extremely narrow minded, tiny and quite frankly utterly useless set of mathematical operators, does n=np? The answer to which I think is probably no. With any restriction on the toolset, you're digging your own grave. Nice vid Brady, you're a legend!
Wow, you think very deeply about the Simpsons! I figured ‘P’, ‘NP’ or any other mathematical statement is just there to add effect, rather than a subtle declaration of a philosophical point of view!
I seem to recall 1 or 2 more mentions in tv shows of N=NP. I forget where it was but I remember it was somewhat out of character for them to mention such. And I agree P is not NP. My intuition of NP is that it's combinatorial and in its pure form it's like guessing a code blindly, you have to try all possible combinations which is exponential time.
As a benighted physicist im curious: What about Shor's algorithm which turns prime factorization into a p problem on a quantum computer? Doesn't that show that at least some np problems can become p problems?
You HAVE TO make a video about NP-Complete type of problems and Cook's theorem. Otherwise the whole discussion about P and NP and the possibility that P=NP makes no sense.
You guys should have touched upon the fact on how this is the basis for all modern encryption! Maybe people would stop saying this belongs in numberphile :)
I originally had the understanding that NP is simply that it can not be computed in a feasible time scale say 1000+ years with out having the solution to the answer.
He definitely should have mentioned this in the video. There's no mention of the real application of this at all. It's quite an awful explanation, to be honest.
Certain problems (say, doing a linear search on a list) are relatively easy to do and scale pretty well as the numbers get large, so for searching through a linear list, the worst case is that you will need to check one more number if the problem increases by 1 (i.e. its at the end). We would say this problem has linear complexity (i.e. efficiency), the formal notation here is O(n). Other P problems ones have complexity log n, or are polynomial i.e. n^2 or n^3 etc. NP problems are ones which scale badly as the numbers get large - this is easy to see when you consider that the problems will be of exponential complexity or worse (i.e. 4^n or 5^n) - so imagine a problem with 100 'things' in it - if the problem is linear, thats not too bad, but if its exponential (NP), then that might be 4^100 which is very big indeed, and a lot bigger for 101, 102 etc...
Hmm. Honestly I was hoping this went in much more depth....but once I saw that the running time was less than 6 minutes I was like, "Ya this will be barely touching the surface of this subject" Oh well, maybe an expanded video talking more in depth about this subject would be cool someday!
The Simpsons' P vs. NP reference is however on screen at the same time as the false Fermat counterexample! So, is the Simpsons really saying P = NP or not?
I think a bit more in depth explanation would be cool if anyon you know is up for it brady. Also the reason most mathematicians believe np and p are not the same is because they must prove it is impossible for all np problems. Thankfully this is made a bit easier because while all np problems are different (taveling salesman, world maps, factoring) each and every known np problem can currently be represented equivalently as a certain type of np problem called a clique. And finally, I think that np problems get more difficult because the number of operations on average needed to solve a problem. A factoring problem you basically go through a strategic set of numbers till one works. Np problems have an estimated solution that is x to the n or O(n) not exactly sure which is proper. Regular p problems solve with x to the k steps or O(k) where k is some constant.
P as the class of problems solvable by a deterministic Turing machine in polynomial time. NP as the class of problems solvable by a nondeterministic Turing machine in polynomial time.
So is there a boundary where when you add one digit more the problem comes NP instead of P? Or do all these kinds of problems have a P side to them and an NP side and the proportions differ when numebers get bigger?
I don't know if you could translate NP into P, but that at least N.P. gives the A.I. guys a good justification to work, which is nice since A.I. is my favorite part of computer science.
its not simply how large the numbers are but how many possible options there are to check assuming a brute force type approach. similar these two concepts are similar but different.
I think this needed a video on big-O notation and the meaning of computational complexity so we could properly get into the meat of the P vs NP problem - as it stands, I think anyone new to the idea will soon forget it again because the definition of "hard to solve" isn't cemented in their minds.
Is it 'either they are equal or completely different' for sure? Isn't it 'either they are equal or the class of P problems is subset (not equal) of NP or not'? I'm just asking as a computer science student.
This is only a simplified explanation, but not exactly correct. I think here what you are trying to say by NP is NPC (NP-complete). NP is problems that can be solved by non-deterministic methods in polynomial times (another definition is "problems whose instances can be checked within polynomial time"), while P is by deterministic ones. NPC is one part of NP, and any NP problem is reducible to NPC, e.g. traveling salesman problem, while SAT is the most simple one. P belongs to NP,so does NPC, no matter whether N = NP. If N = NP, N = NP = NPC. So if N=NP, we can solve any NP problems in polynomial time, a nice thing. NP-hard is problems to which any NP problem is reducible to, but NP-hard itself is not NP, e.g. the method to always win in chess game. Whether NP equals to P is one of the Millennium Prize Problems, but someone has already claimed to have proven NP != P. The proof is still under validation.
I was expecting more of a detailed explanation between P = NP and P ≠ NP. Why do both writers (Cohen and Westbrook) include both despite the difference between the two?
I know an NP-Complete joke, but once you've heard one you've heard them all.
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 :)
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
Does ANYONE read the existing comments before adding their own?
Anyone? :)
>Brady
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.
Troels Vincent Yes that's a good point actually; that equation is an example of Fermat's Last Theorem.
The day P=NP is the day that all modern encryption schemes are broken!
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
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.
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.
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
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.
If I'm not mistaken, P=NP also appears in the same scene as a slightly modified version of Euler's identity e^πi=-1. Wonder what that implies...
Well, how's it modified? If it's slightly incorrect, then it fits in with the Fermat near-miss and strengthens my case for the writers not believing P=NP.
It's not incorrect, just a rearrangement of numbers. In fact, e^iπ+1=0 and e^πi=-1 are both correct.
In the book "Simpsons and their mathematical secrets", it is stated that Davis S(/X) Cohen is in fact a supporter of P=NP. As I understand it, this is backed by actual interviews.
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.
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!).
"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) .
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.
Just a short of clarification (you may delete this if it was written before... I didn't see it and I really tried to find something that actually explains the classes and defines them):
* Decision problems in P (such as Path finding or Prime test (yes it is in P)) are called Deterministic Polynomial Time problems because there exists a Deterministic Turing Machine that can be solve the problem in a polynomial time.
* Decision problems in NP are problems that, for a given solution, you could check in a polynomial time if the solution is correct. For instance: Hamiltonian path is in NP because you really have to check all possible paths to see if the graph has a Hamiltonian path in it. However, given a set of nodes and a graph, you can check in a linear time if that set of nodes is a Hamiltonian path (linear is a polynomial of the first (1) degree). So - problems in NP are problems that a solution to them could be verified in a polynomial time. This doesn't explain the NP which is Non-Deterministic Polynomial time. The second definition of NP is the set of all problems that could be solved in a polynomial time on a NON-deterministic Turning machine.
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.
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 =/)
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".
they cant solve my memes
I like the video. I wish he would assume the viewer understood exponents. Most people do if you use the right terminology -- square-footage over your home, number of marbles in a jar, etc.
To a layman I would give examples of searching a linear list is is "N" time. Sorting a list is "N squared". Or N to the second power. Second power is a simple number, 2. It could be 3 or 4, and it would remain P. But if the complexity is relative to the size of the problem space, such as "to the N power" for N elements, then it becomes NP. This is actually not a great definition in scientific terms. This is just a property of NP, but that's not what makes it NP. However, it's enough for someone with just some high school Math to grasp the difference.
I'm a software engineer & I've studied this a lot, so I think I can clarify this. P means it can be worked in linear loops, like w/ Bubble Sort, if you have 10 numbers, you compare each of the 10 numbers to each of the other numbers, so it's 10^2 or 100 comparisons. NP is like 10^N, so if N=10, that means 10000000000 comparisons or other operations that must be performed & your computer may crash before you get done :) Are they the same????? Well, what do you mean by that, eh? They are conceptually different; however all of these algorithms are intended to work out some useful task as it relates to the real world (designing a better engine, or maximizing efficiency of your business, etc). We call this "the problem you are working on." Now if you spend enough time studying the fundamental problem you're working on, you can often find a different approach, or an approximation of the original approach that that is P not NP. For example one of my professors found an algorithm that was N^10th power whereas the previous fastest algorithm was exponential (like 10^N). Therefore, mathematically, they are fundamentally different, but you can sometimes use P to approximate NP (like Taylor polynomials in calculus), or you may give up on the approach you've been taking to solve your problem & find a better approach that is P instead of NP.
And BTW, there was a paper while back talking about when they come out w/ Quantum Computers, they will factor large numbers very quickly, which means most of the encryptions on the internet will have to be changed, but many NP problems will stay NP hard - like trying to get a computer to work out mathematical proofs for you - it's a N! problem & Quantum Computers would only speed that up slightly.
The only thing I learned from this video is that NP problems are exponentially harder to do than P problems.
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.
I believe this topic belongs to Numberphile more than to Computerphile even though it is about computational complexity. It's a mathematics discipline more than computer science as many P problems are still too impractical for computers. Imagine you have an algorithm which works in N^80. It ends quite fast if N=1, but even for N=2 it suddenly lasts quite a while and for N=100 all the computers in the world will not help you calculate it in time.
The matter is, all NP-hard problems are equal. I.e. they can be converted to each other in polynomial time. If a polynomial solution is found for one, it's found for all of them.
I get why you said that shoul be in numerphile, but this is still a computer problem, computer science is not only about computers but also about the theoric aspects of it, so even in this problem is mainly a math problem I belive is still full related to computer, just my thougt.
bnightm XD I was about writing the same expression, and yes that pretty accurate, I'm a CS student, congrats to you that already have your bachelor ;)
*cough*NP-complete*cough*
NP-hard contains, among others, exponential-time and factorial-time probelms.
bnightm
I don't know that the thought was original, but I've always heard this attributed to Dijkstra's quote that the name "computer science" is "like referring to surgery as 'knife science'".
I think this would be an interesting topic for a more general Computerphile video. When I was doing my degree there was a lot of pressure from certain directions to reduce the volume of mathematics, logic and theory of computation in favour of so-called "practical skills", which seemed to mean learning more industry-favoured programming languages. In my life since I've found that people tend to equate my CS degree with being able to fix their printer or help them send an email.
In my view complexity classes and computability lie at the very core of computer science, but I'd love to listen to some of the Computerphile contributors' thoughts on the topic.
udscbt You're right, of course. Sorry about it, I was taught these things in another language and I don't always know the right english name for them.
Don't go to Audible if you're a Linux user, incidentally - they don't support Linux at all.
The N and P deal with, as I understand, the number of steps or calculations that need to be taken to arrive at a useful solution. The whole premise leaves out the idea of formulating a new and more appropriate algorithm. Let's look at the Chess simulators, or chess player games, because those are a good example. If you want a good example of an uncomputable problem, look at a chess game after five moves. So you need to include the idea that you trim the tree of possible outcomes. This is one way you can attack, computationally, a problem of almost infinite complexity. Same for the travelling salesman problem. It might prove to be almost impossible to calculate all possible alternative solutions to find the single shortest, but you can prune a hell of a lot of possibles out within 3 or 4 moves. Like the boys at Bletchly Park showed with Enigma, you don't brute force the thing, you look for cheats and hints and ways to trim the field of possibles. The trick, the art, is finding a way to do the thing that doesn't expand at N ^ M ^ M .... The trick is to find algorithms that don't 'explode' in progress. Many things seem at first, as if they must. Chess is one good example.
Exactly, like alpha-beta pruning in MiniMax game trees.
Or knowing how many zeros there are in 1000! By using cheats and math shortcuts. It is a point where art, science, and out-of-the-box thinking meet.
In simple terms, NP means that the problem is "easy" to check, while P problems are "easy" to check and to compute the answer to.
our current understanding of the subject indicates that being "easy" to check is not enough to be "easy" do compute, at least not with a normal computer processor. This is important, since it's the basis on which the convenient kind of cryptography we use everywhere can work at all.
Here's a proper explanation of the P vs. NP problem. The video is, simply, incorrect.
We say a problem is "in P" if it can be solved in "polynomial time" - that is, the running time of the solver grows as a polynomial function, not, say, exponential. (That is, the running time t(N) is less than cN^d, for some constants c and d where N is the size of the input to the problem.) We (arbitrarily) say these problems are easy, though of course if c or d are large, they may take a long time to solve. In simple terms, a problem is in P if it has a "fast" solver.
Now, suppose I give you a solution to any problem, and asked you to tell me if my solution was correct. You would come up with a "verifier" that checks if my solution is valid. If your verifier itself runs in polynomial time, we say that the problem I solved is in NP.
This has the consequence that *any* problem in P is in NP. If I give you a solution, you could simply run the solver algorithm to check if my answer is correct. The P vs NP question is asking whether it is the case that if a problem's solution can be checked easily, the problem can be *solved* easily.
Concretely, consider factoring. At present, there is no polynomial time solution for factoring a large number - this problem is hard. However, suppose I gave you two numbers I claim are factors of a larger number. You could check this easily by multiplying my factors together and verifying they do, in fact, produce the original number. Because this verification is easy, we say factoring is in NP.
To summarize - All problems in P are in NP. If the reverse is true (all problems in NP are in P) then we have shown that P=NP. The video suggests that P problems are easy and NP problems are hard, but in fact this is not true.
Someone asked "what's the mathematical definition of an NP problem?"
The best answer I can give is its a problem where the best known method of solving would take on the order of the age of the universe to work out for some sufficiently large input. All algorithms have an asymptotic running time complexity, that is, the time it would take to solve given some input of size X where X tends to infinity. For example if I want to sum a series of numbers that is X numbers long that would take T=X time (one time unit for each number I want to add). A series 10 numbers long takes 10 time units, 1,000,000 numbers long takes 1,000,000 time units and so on. If you were to graph this out with size of the input on one axis and the time it takes to solve on the other axis you would get a straight line so we say this takes linear time. If I change the the problem slightly and now say I want to sum some series of numbers in a matrix that is X numbers by X numbers in size it will now take T=X*X or T=X^2 time (X time for each row multiplied by X columns). Now if I I plug in X=10 it takes 100 time units to solve and if I plug in 1,000,000 for X it takes 1,000,000,000,000 time units to solve. If we were to graph this function you would get the graph of X^2 which you can see grows much more quickly than the graph of T=X. This means that a solution that runs in X^2 time will take MUCH longer to run when X gets sufficiently large. With NP type problems we don't have running times of X or X^2 which are general considered "pretty good" but more like a^X (where a is some integer) or X! or X^X which grow extremely rapidly and even with "modest" size inputs would take the best supercomputers trillions of years to solve. I'm not sure that there is a hard, fast line in running time complexity where we say "that's an NP problem" but if after doing the math you find out the best known algorithm to solve your problem will take something like the age of the earth to run then chances are you have a candidate NP problem.....or a really crappy algorithm (which brings us back to the whole question does P = NP, is the problem truly unsolvable in any reasonable amount of time or have we just not found the right algorithm to do it?).
I haven't read all the comments, but I don't believe this has been said yet. Factoring large numbers is an O(sqrt(N)) problem, not an NP problem.
Factoring is indeed an NP problem because it has a verifier that runs in polynomial time (simply multiply the two factors together). I think what you mean is that it is not NP-Complete, in which case you are likely (though not certainly!) right.
You are correct I phrased that poorly. What I meant was that factoring is an O(sqrt(n)) problem, and therefore a solution to p vs np would not have an implication for our ability factor numbers quickly.
Actually, this is a common misunderstanding - factoring is not, in fact, O(sqrt(N)). The reason for this is that the size of the input is defined to be the number of bits required to represent it, not the magnitude of the number. The number of bits needed to represent arbitrary N is B = log_2(N). The factoring algorithm you suggest is O(sqrt(N)) - since N=2^B, your algorithm is O(sqrt(2^B)) = O(2^(B/2)) and is therefore exponential, not polynomial.
Correct me if Im wrong but I think the increase in time taken for a program to find all factors of a number N could be less than the proportional increase in N ie for large N t1= f (n) t2=f(2n) t2 < 2t1.
My thinking is that first the number of potential primes to check would increase at a slower proportional rate than the size of root N. Bigger than root N don't need to be checked and prime numbers become less frequent the larger you go.
Second if N is a factor of 2 larger it only takes 1 more bit to store it so thats not a problem .
Third the factor test could be done by approximating a number to multiply by and subtracting the multiple from InI until close enough to run through taking the prime from n until n is 0 or negative. The time to check could increase at a slower proportional rate than the size of N and could be roughly proportional to a log function of N so increase at a rate less than root N.
combined for large N you get (less than root N)^2 + log base 2 (N) .
luaudesigndf Shows it can be done. I wouldn't stand a chance solving any of those though the best I could do is run calculations on an int or long in vb and hopefully get a less than linear increase in difficulty as the numbers scale.
I think P=NP is accurate myself, because where would you draw the line between "easy" and "hard" which are both subjective terms. That line moves around for every person.
Certainly in his example 15 is much easier for most people to factor, but as you increase the number, who's to say if one person starts moving into NP territory at one point while another continues on for quite a while before it becomes NP for them.
This is the what I read about the P vs NP problem (which probably isn't entirely true):
P computational time: ∝ inputs to a number (e.g. inputs^ 5)
NP computational time: ∝ a number raised to inputs (e.g. 2^ inputs)
This is how I visualized what was written:
On a log(time) versus inputs graph, the slope of P problems decrease with time while NP problems form a straight line.
On a log(time) versus log(inputs) graph, P problems form a straight line while NP problems curve upward.
I've been waiting for this video for literally two years now.
For clarity, I think that one should refer to "(N)P-type calculations". If P = NP, then a "hard" problem might have one means of solution that is NP but it also has a solution that is P; it would be a misnomer to label such a problem as being an NP problem, since it is actually a P problem and only a given calculation for it may be NP. If P =/= NP, then the issue does not arise (since all problems that have P solutions are P problems and all problems that have NP solutions also lack P solutions and thus are fundamentally NP problems). But, since the conjecture has not yet been determined, we should make our language deliberately careful.
At the end of the video Mr Singh says that the difficulty of factorization increases as the numbers get bigger. Factorizing a 3 digit number is clearly more difficult than a 2 digit number, but my question is: there is a way to measure the increase in difficulty of a problem? I mean, is there a sort of function for difficulty, which tells us exactly how difficult a problem is?
Merione1996 Yes, it's called Big O Notation. And it mostly determined by the number of loops required to solve a problem.
The time you have to wait to get the result from the computer
Oh man, I was so excited when I saw the title of this video and then you come up with a video that explains very little but repeats common misconceptions instead :(
I mean if NP were "non-polynomial problems" then the whole "Is P=NP?" debate would be over before it began. Also, it's not "some problems" from NP that might "jump over" to P, it's all or nothing (either P is a subset of NP or it is the same set).
Having never encountered the terms P and NP before, and seeing this first thing in the morning, my brain assumed we'd be talking about transistors.... BRAIN FAIL. But great intro to the subject!
Would it not be less ambiguous to define "solving strategies" as being either P or NP, instead of the problem itself? What I mean is that the difficulty of finding a solution is not necessarily depending on the question (problem), but on the way (strategy) you find the answer (solution).
By such a redefinition of P and NP, finding the factors of a number (121=11x11) is only an NP problem when using the current strategies to find the solution, would a strategy (algorithm) be found to solve this in P time, then only the new strategy becomes P, the old strategy is still NP. But the problem has shifted from NP to P, because there is a strategy in P for the problem.
Complexity Theory is a computable extension of the Turing Machine itself.
NP vs P is the nonsensical statement by which two logical arguments contradict each other only to balance and imbalance themselves out indefinitely. Its the limitation of the frame in and of itself which makes the technique find its boundary - its the end of boolean logic in the same sense Godel spoke about incompletitudes in formal logic.
You want to solve NP vs P you have to kill-off the turing machine and start over again with something else - maybe an Oracle Turing Machine with a diffuse switch which stochastically resets the machine so it can reframe itself with different components until the problem in hand is solvable.
This problem will never be solved with the TM.
As problems increase in difficulty, it there a gradual transition from P to Non-P, or a distinct step; or are they fundamentally different in some way?
The example given, Factoring, is not known to be NP-complete. Indeed, it may be in P but there may be other problems that are not. NP-complete problems, such as 3-SAT, are known, such that if 1 can be shown to be in P, then NP=P.
ah, why is somebody explaining things on TV which he doesn't understand (according to his own admission?)
(OK, actually watched the video) He doesn't really say NP-hard or -complete though, he just says NP. As long as there is no P algorithm for it... that's fine. But I guess it's not the typical example one would use.
Actually NP stands for "nondeterministic polynomial". Which means that if you (or a nondeterministic turingmashine) always guess correct, you can solve the problem in polynomial time. So guessing and checking if The guessed solution is correct both are polynomial.
And btw, since Simon uses the phrase "NP hard" several times: There is a subtle difference between "NP", "NP hard" and "NP complete".
Thank you for explicating that points. :-)
It seems to me that "NP means nonpolynomic" is an easy and widespread misconception.
And of course a nondeterministic Turing machine is purly theoretical, but so is a regular Turing machine. ;-)
But that's things you have to handle with when talking about complexity and (in my opinion) it's the fascinating insides of that mysterious "NP" everyone talks about. %-)
I know this only was meant to be a rough overview and no introduction to complexity theory. I'm sure in *that* video everything will be fine. :-)
Robin
It's worth noting that NP does not stand for "Non-Polynomial" but for "Non-deterministic Polynomial." This is because it's the class of problems which can run in polynomial time on a non-deterministic Turing machine.
yeah I confirm it
Yea but for encryption to remain valid once we have better quantum computer we are going to need to switch to EXP based encryption so the machine wont be able to keep up with the complexity
A full video on the topic and distinction of P vs NP (and NP-C) would be great for the channel.
From what I understand, the factoring problem becomes more difficult because keeping track of primes becomes more difficult. It is easy as long as all possible prime factors are known in a list. But once you start dealing with numbers which could be squares (or higher) of primes that you are unaware of, the problem reduces to the problem of finding primes.
I might also add that one demonstrates a problem to be an NP problem by reducing it to a known NP problem.
P is the set of all problems solvable in polynomial time.
NP is the set of all problems with answers that can be checked in polynomial time.
If we had a problem A in which all NP problems can be reduced to it (in polynomial time) so that a solution for A will solve them, A is said to be NP-hard.
Now if someone ever finds just one problem that is both an NP-hard problem, and a P problem, P = NP
There's also a book in Futurama called "P=NP".
0:25 NP is not "Non-polynomial"
Btw, NP function referring to the solution still grow in polinomial time, they are just non determinstic.
In our world, computers cannot infinitely multiply on each branching step, so they have to simulate each instance of non-deterministic one. And this number is growing exponentially.
Yep, you are rigth.
P=Problem
NP=No Problem
P is NOT NP...
More like
P = Piece of cake
NP = Not Piece of cake
P as the class of problems solvable by a deterministic Turing machine in polynomial time.
NP as the class of problems solvable by a nondeterministic Turing machine in polynomial time.
Cheers, Brady! I'd love to hear more from the professors about this because it has fascinated me for ages.
P ≠ NP actually means P ⊂ NP, since all P problems are (obviously) in NP. We know perfectly well how to solve "some" of NP problems in polinomial time, we don't know if we can do that for "all" of them. What the video is actually referring to is NP-complete problems, NP problems that we don't know how to solve in P.
Like some of the people in the comments, I got the feeling that I probably know more about P=NP than Simon Singh does, but I still enjoyed this video. It's pretty clearly not a technical overview of computational complexity theory. He was on the money when it comes to the spirit of the topic and even he is clear that he isn't a professional, so no one is being misled.
I had a subject in university called Graph theory and on time we had to write some code to calculate a solution for the "Traveling salesman problem" (find the shortest path for a person so that (s)he visits a certain amount of cities which distances you all know). It was easy for a few cities (something like 6 or 7) but the more you add the harder it gets. You can find an approximate solution but if you want to know the true answer you will have to check all n! possibilities and pick the shortest one (6! = 720, 7! = 5040, 8! = 40320, 9! = 362880). It just gets too hard to quickly. I really like thinking about solving this one day like an easy P problem but until then we have to live with it :)
Shows up in Sims 3 as well. It is one of the "solve the unsolvable" results.
Indeed NP hard problems might be solvable with an algorithm that does not have a polynomial time solution like e.g. order n^3 but perhaps n exponential time like 2^n, any problem that has an algorithm where the time complexity for solving it (in terms of the size of the input n) is greater than polynomial is said to be NP hard. The group of NP hard problems that can be reduced to each other (i.e., if I can solve one problem I can solve the other by 'massaging' the solution in polynomial time) is said to be the group of NP complete problems.
if you guys are interested in the consequences of N = NP, you should see the videos about security and encryption using multiplication of primes numbers
I was expecting a nod to the show Numb3rs, where the main character sometimes is working on this exact problem in his garage. There is a beautiful episode (can't remember which one) where he is very upset by something and hides in his garage for days on end, just working on P vs NP. In the end he is convinced P vs NP cannot be solved
P (polynomial) problems are problems solved in polynomial time, the traveling salesman problem is a NP (non-polynomial) problem where you don't know how long it takes to solve it, so it's solved in non-polynomial time.
The question is, if there is any way to solve the traveling salesman problem in polynomial time, for example an algorithm.
The only way of solving the traveling salesman problem currently is to check every possible salesman way and see which is the shortest.
"You can't solve a problem by the same line of thinking that caused it" Einstein
The biggest problem of P vs NP is how it is framed. Since solving P vs Np is an "NP problem" there is no mechanism for solving it without the answer.
Reframe the thing as an informational problem and figure out how you can frame it in a way where you can use Claude Shannon's informational entropy and it will become solvable.
Not easy, but solvable.
so to clarify, is it that a "p" type problem has a low number of factor?
ex: 20= 4x5=2x10
and an "np" type problem as many?
ex:104,856,007,582,823,786=(a shit ton of combinations of factors)
If you wanna see an amazing and accurate video on this topic, look to your right.
You'll probably see (if not, search) a video titled: *P vs. NP and the Computational Complexity Zoo*
Just watch it right away, I assure you it will be the best short video you'll watch on this topic.
This is the most fascinating question I've ever come across.
I personally think that all problems are inherently as difficult as each other, and it comes down to the tools you're using to solve them. There is no “p vs. np” from the standpoint of infinite toolset, since every problem can be solved in constant time, there's a tool that simply gives you the answer.
The real question we're asking with “p=np?” is, granted our extremely narrow minded, tiny and quite frankly utterly useless set of mathematical operators, does n=np? The answer to which I think is probably no. With any restriction on the toolset, you're digging your own grave.
Nice vid Brady, you're a legend!
Watching this a few years later when I first watched it, I am able to get my head round this.
Wow, you think very deeply about the Simpsons! I figured ‘P’, ‘NP’ or any other mathematical statement is just there to add effect, rather than a subtle declaration of a philosophical point of view!
Btw: NP is not "not-polynomial" But "non determined polynomial".
In the Simpson’s cel showing P=NP there is also a false equality contradicting Fermat’s Last Theorem. Don’t jump to conclusions.
Simon Singh is great; you should have him on as much as possible..
I seem to recall 1 or 2 more mentions in tv shows of N=NP. I forget where it was but I remember it was somewhat out of character for them to mention such.
And I agree P is not NP. My intuition of NP is that it's combinatorial and in its pure form it's like guessing a code blindly, you have to try all possible combinations which is exponential time.
As a benighted physicist im curious: What about Shor's algorithm which turns prime factorization into a p problem on a quantum computer? Doesn't that show that at least some np problems can become p problems?
You HAVE TO make a video about NP-Complete type of problems and Cook's theorem. Otherwise the whole discussion about P and NP and the possibility that P=NP makes no sense.
brady i didn't know you had this channel too. that's cool man. keep up the great work!
You guys should have touched upon the fact on how this is the basis for all modern encryption! Maybe people would stop saying this belongs in numberphile :)
P vs. NP also appeared in an episode of Elemantary
Mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
indeed, Season 2, Episode 2 - Solve For X, if you're curious...
I originally had the understanding that NP is simply that it can not be computed in a feasible time scale say 1000+ years with out having the solution to the answer.
And thats why these kinds of problems are used as Proof of Work algorithms
He definitely should have mentioned this in the video. There's no mention of the real application of this at all. It's quite an awful explanation, to be honest.
Does ANYONE read the existing comments before adding their own?
Simon Singh! I didn't know it was him at first. :) Such an excellent author.
I've watched this twice and I'm still not getting an explanation as to what P and NP problems actually are. I'm left really confused
Certain problems (say, doing a linear search on a list) are relatively easy to do and scale pretty well as the numbers get large, so for searching through a linear list, the worst case is that you will need to check one more number if the problem increases by 1 (i.e. its at the end). We would say this problem has linear complexity (i.e. efficiency), the formal notation here is O(n). Other P problems ones have complexity log n, or are polynomial i.e. n^2 or n^3 etc. NP problems are ones which scale badly as the numbers get large - this is easy to see when you consider that the problems will be of exponential complexity or worse (i.e. 4^n or 5^n) - so imagine a problem with 100 'things' in it - if the problem is linear, thats not too bad, but if its exponential (NP), then that might be 4^100 which is very big indeed, and a lot bigger for 101, 102 etc...
This video doesn't really explain it. I suggest you find another source and be patient.
Amazing video! I've heard about P=NP for ages, but only now do I understand it. Thanks Simon! :)
Hmm. Honestly I was hoping this went in much more depth....but once I saw that the running time was less than 6 minutes I was like, "Ya this will be barely touching the surface of this subject" Oh well, maybe an expanded video talking more in depth about this subject would be cool someday!
The Simpsons' P vs. NP reference is however on screen at the same time as the false Fermat counterexample! So, is the Simpsons really saying P = NP or not?
I think a bit more in depth explanation would be cool if anyon you know is up for it brady. Also the reason most mathematicians believe np and p are not the same is because they must prove it is impossible for all np problems. Thankfully this is made a bit easier because while all np problems are different (taveling salesman, world maps, factoring) each and every known np problem can currently be represented equivalently as a certain type of np problem called a clique. And finally, I think that np problems get more difficult because the number of operations on average needed to solve a problem. A factoring problem you basically go through a strategic set of numbers till one works. Np problems have an estimated solution that is x to the n or O(n) not exactly sure which is proper. Regular p problems solve with x to the k steps or O(k) where k is some constant.
P as the class of problems solvable by a deterministic Turing machine in polynomial time.
NP as the class of problems solvable by a nondeterministic Turing machine in polynomial time.
So is there a boundary where when you add one digit more the problem comes NP instead of P? Or do all these kinds of problems have a P side to them and an NP side and the proportions differ when numebers get bigger?
I don't know if you could translate NP into P, but that at least N.P. gives the A.I. guys a good justification to work, which is nice since A.I. is my favorite part of computer science.
its not simply how large the numbers are but how many possible options there are to check assuming a brute force type approach. similar these two concepts are similar but different.
talk about this more.
I think this needed a video on big-O notation and the meaning of computational complexity so we could properly get into the meat of the P vs NP problem - as it stands, I think anyone new to the idea will soon forget it again because the definition of "hard to solve" isn't cemented in their minds.
Upcoming Computerphile? Quantum computers? I hope so...
If you would be able to transform NP into P problem, you would rule the world.
Is it 'either they are equal or completely different' for sure? Isn't it 'either they are equal or the class of P problems is subset (not equal) of NP or not'? I'm just asking as a computer science student.
This is only a simplified explanation, but not exactly correct.
I think here what you are trying to say by NP is NPC (NP-complete).
NP is problems that can be solved by non-deterministic methods in polynomial times (another definition is "problems whose instances can be checked within polynomial time"), while P is by deterministic ones. NPC is one part of NP, and any NP problem is reducible to NPC, e.g. traveling salesman problem, while SAT is the most simple one.
P belongs to NP,so does NPC, no matter whether N = NP.
If N = NP, N = NP = NPC. So if N=NP, we can solve any NP problems in polynomial time, a nice thing.
NP-hard is problems to which any NP problem is reducible to, but NP-hard itself is not NP, e.g. the method to always win in chess game.
Whether NP equals to P is one of the Millennium Prize Problems, but someone has already claimed to have proven NP != P. The proof is still under validation.
Finally, a clear explanation for the rest of us.
Would a Log(N) process be NP then? Wouldn't it grow "slower" then an O(N) i.e. polynomial process?
THe long awaited movie about the most interesting things in cs. Thank you!
I really want that guys glasses, except in silver rather than gold.
I was expecting more of a detailed explanation between P = NP and P ≠ NP. Why do both writers (Cohen and Westbrook) include both despite the difference between the two?