P vs NP on TV - Computerphile
Vložit
- čas přidán 7. 02. 2014
- Audible free book & trial at: www.audible.com/computerphile
Our thanks to them.
P vs NP in The Simpsons and Futurama. Featuring author Simon Singh.
simonsingh.net
Simon on Numberphile: bit.ly/SimonSinghPlay
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.
/ computerphile
/ computer_phile
Film by Sean Riley and Brady Haran.
See the full list of Brady's video projects at: bit.ly/bradychannels
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 only thing I learned from this video is that NP problems are exponentially harder to do than P problems.
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 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.
they cant solve my memes
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.
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 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.
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've been waiting for this video for literally two years now.
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.
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.
Don't go to Audible if you're a Linux user, incidentally - they don't support Linux at all.
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.
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!
Does ANYONE read the existing comments before adding their own?
Amazing video! I've heard about P=NP for ages, but only now do I understand it. Thanks Simon! :)
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.
Watching this a few years later when I first watched it, I am able to get my head round this.
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".
A full video on the topic and distinction of P vs NP (and NP-C) would be great for the channel.
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?
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
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.
There's also a book in Futurama called "P=NP".
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.
Shows up in Sims 3 as well. It is one of the "solve the unsolvable" results.
brady i didn't know you had this channel too. that's cool man. keep up the great work!
Upcoming Computerphile? Quantum computers? I hope so...
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.
This video actually explained this problem to me simply! Thanks!
Really liked this video. As ever Simon explains things very clearly and simply.
My university project was actually on metaheuristic algorithms to find "good enough" answers to non-P problems. Maybe I can link to this on my CV ;)
"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) .
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
This guy can create a shadow in the form of a pineapple.
Could you guys do a video which explains the differences between Geometric vs Exponential Growth? It seems more common with older science fiction writing that they use the phrase "Geometric Growth" when talking about a process that increases exponentially over time, but I've heard the two phrases used almost interchangeably. Since I don't fully understand the differences between the two, I just consider them to be two ways of saying the same thing when I come across them. This might be a better question for Numberphile now that I'm thinking about it.
THe long awaited movie about the most interesting things in cs. Thank you!
0:25 NP is not "Non-polynomial"
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.
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.
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
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
I would love more videos on this topic. Also, I think a video on quantum computers would be awesome.
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.
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.
Btw: NP is not "not-polynomial" But "non determined polynomial".
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?
Simon Singh! I didn't know it was him at first. :) Such an excellent author.
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.
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)
Can you do a video explaining the latest paper about p=np?
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 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.
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 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.
Thank you Simon
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.
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
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?
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.
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.
P vs. NP also appeared in an episode of Elemantary
Mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
indeed, Season 2, Episode 2 - Solve For X, if you're curious...
Hi ***** you might wanna explain where the p and np come from, meaning the order of different problems O(n) , O(x^n) and so on.
Would a Log(N) process be NP then? Wouldn't it grow "slower" then an O(N) i.e. polynomial process?
I really want that guys glasses, except in silver rather than gold.
Simon Singh is great; you should have him on as much as possible..
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.
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.
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.
Oh they had an episode of Elementary where they featured this,
Learned about P versus NP in Elementary.
Just about to google it.
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!).
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.
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'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.
there was also an episode of Elementary related to P vs NP. Just fyi.
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.
Popular interview question, currently.
At how many digits a number became NP?
personally square roots and roots in general were a terrible nightmare for me when i tried to go to college, i tried learning an algorithm to figure it out on paper.
He looks like the guy from back to the future!
I think he made the Futurama one way more deep than it was. The background is more of the animator's area.
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 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.
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.
Finally, a clear explanation for the rest of us.
Does anyone actually read the existing comments before commenting? ;)
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 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.
I notice this when routing traces on a circuit board, easy to know you have a mistake (eg clearance error) but much harder to know the solution. Even $10k software that only knows how to route traces require a lot of human interaction.
Also if NP=P then wouldn't that break many cryptographic algorithms that are based on a solution requiring little computing power to check but an enormous amount to solve?
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.
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.
I'm regularly watching Computerphile, Numperphile, Vsauce, Veritasium, Minutephysics etc. I'm starting to wonder what the heck am I actually doing with my brain? lol