6 ms·

Ask HN: Explain to me the theory behind P=NP in simple words

11 points by orionblastar 14y ago

I studied Computer Science at Um Rolla (Now Science and technology) and never was told how the P=NP theory works without people using nonsense and stuff that doesn't make any sense (Teacher's Assistants covering for professors who don't understand it taught it). I find that there have been a few attempts at proving P=NP but later were found to be false. No two people I met can use the same definition of the theory to me. I feel that everyone I communicate with who claims to understand the theory is just BSing me. I want to know the truth, and I want it in simple words so it is easy to understand. Any help?

tlarkworthy 14y ago
Well its not proved so there is no theory, only conjecture. P is polynomial time algorithms, O(n^k) runtime for some k. Algorithms you can run on reasonable sized inputs. NOT O(k^n) exponential time algorithms. Often a hard algorithm like finding the most efficient route through a city, can only be optimally solved by trying every combination of route. Thus, it's runtime is exponential in the number of inputs. However, if there existed a computer that could make lucky guesses, it could just guess the correct route and verify the answer. NP algorithms are Non-deterministic algorithms (guessers) that can solve harder problems in Polynomial time, like combinatorial problems. It is thought P != NP (for obvious reasons) but no-one can prove it. The philosophy of the conjecture is that some algorithms are fundamentally harder than others, but we can't prove it yet.
- idupree 14y ago
  We know that some algorithms are fundamentally harder than others. Deciding whether two regexps are equivalent requires EXPSPACE which is known to be a strict superset of NP[1]. We just haven't proved whether P != NP. [1] https://en.wikipedia.org/wiki/EXPSPACE https://en.wikipedia.org/wiki/EXPSPACE
  - orionblastar 14y ago
    It makes no sense to me. Please explain it in your own words using simplified terms.
idupree 14y ago
Are Wikipedia's explanations clear enough to you? Too long? Too formal or informal? https://en.wikipedia.org/wiki/P_versus_NP_problem https://en.wikipedia.org/wiki/P_versus_NP_problem
- orionblastar 14y ago
  The Wikipedia article makes no sense to me. Please explain it in simple terms using your own words.
  - qbrass 14y ago
    http://simple.wikipedia.org/wiki/P%3DNP http://simple.wikipedia.org/wiki/P%3DNP Try that one.
    - orionblastar 14y ago
      Sorry clear as mud to me. I don't understand that one either.
    - deleted 14y ago
      [deleted]
    - alok-g 14y ago
      Seems like guessing a password would be an example. Assuming that the length of a password is N, if the machine can somehow guess the password, it can verify in O[N]. On the other hand, if the password is not known, the number of possible combinations to try would be exponential.
lacker 14y ago
To understand the P = NP stuff, you first need to understand what people mean by "P" and "NP". "P" refers to problems that can be solved in polynomial time. This includes almost all of the normal algorithms that you use in everyday programming, like sorting a list or using a hash table. "NP" refers to problems whose answers can be checked in polynomial time. This is kind of a weird group of problems. Generally an NP problem will be phrased as, "Can you find a solution to this formula?" Like, can you color a given graph using X colors without giving two adjacent nodes the same color? So. The "P = NP" question is whether these classes of problem are actually the same. You can generally solve a find-the-solution-to-this-formula problem by checking all the possible solutions. That takes exponential time, though. The "P = NP?" question asks, is there a general way of solving these problems faster? Most people who have an opinion suspect that the answer is no. That P is not NP, and that there is no fast way to solve general formulas. However, it's really hard to prove that writing a particular program is impossible, and nobody has proven that P != NP. It's a fairly complicated problem definition, so I wouldn't assume that all these folks are BSing you. It's just tricky to explain because it depends on a lot of other knowledge.
- orionblastar 14y ago
  How does one learn this other knowledge when they cannot afford tuition at a high priced university anymore but has a university degree, just not a graduate degree?
  - tptacek 14y ago
    Wikipedia is a good start here.
    - orionblastar 14y ago
      Wikipedia is not a good start for me because I find the articles there on the subjects involved very confusing. It is like they are writing in bad grammar with poor logic and cannot follow any sort of logic I understand. Anything else to use? Don't get me wrong I used to be big on Wikipedia, but over the years it has gotten worse, using unverified sources, taking things for granted without references and citations, claiming it is 'general knowledge' and does not need verification and citations. Every since 2007 they allowed people with fake degrees to cook the facts and statements in Wikipedia articles and now they are mostly nonsense and poor logic and hard to understand for me. http://www.telegraph.co.uk/news/1544737/Fake-Wikipedia-prof-altered-20000-entries.html http://www.telegraph.co.uk/news/1544737/Fake-Wikipedia-prof-...
rsofaer 14y ago
I didn't understand this sort of math at all until I spent some time in a formal Theory of Computation class studying first finite automata/regular languages, then PDA/CFL and other related topics. I don't think you can expect to understand the reasoning that led to the P=NP question without that kind of study. You must learn the math. On the other hand, here's a short summary of P=NP itself: There is a large group of problems called NP (Non-Deterministic Polynomial), which have been shown to be equivalent, in that a polynomial time algorithm for one could be used to construct polynomial time algorithms for all the others. These problems all have the property that a possible solution can be tested in polynomial time. Because NP is big, many of the problems within it are useful, and it isn't intuitively very far from problems which are soluble in polynomial time, a lot of work has been done on trying to either find polynomial time algorithms for NP, or show that no such algorithm could exist. edit: As lacker mentions, one intuition about NP problems is "Problems for which you must check all the possible solutions and see which one is right."
- orionblastar 14y ago
  What is polynomial time and Non-Deterministic Polynomial? Please explain these in simple terms.
  - rsofaer 14y ago
    NDP is what I said above, you can test a solution in polynomial time. You should get an algorithms textbook to read about time complexity of algorithms if the "Time Complexity" page on wikipedia doesn't make sense to you. I used Cormen's textbook in my algorithms class. This is important, you're going to have trouble if you don't really understand the asymptotic (as the data structure gets large) difference between, for example, searching a list and searching a tree.
    - orionblastar 14y ago
      From my limited understanding a list is a data structure that contains an ordered number of items. For example a linked list that has a pointer to the next item in the data structure that keeps the list in order. A tree data structure has sub-sets of linked nodes starting at a 'root' node, much like a tree. How does time complexity fit into that?
sold 14y ago
This video by Mike Sipser (http://www.youtube.com/watch?v=msp2y_Y5MLE http://www.youtube.com/watch?v=msp2y_Y5MLE) might help you. It might be long, but you need to spend a longer time if you are confused. First of all, P=NP is not a "theory"; it's a _question_. We do not know whether the answer is "yes" or "no"; most experts suspect that the answer is "no", i.e. P is not NP. There were attempts to prove it both ways, none successful or even remotely close. The theory encompassing the question is called computational complexity. It is a relatively new field (foundation is often taken to be ~1965), and many questions are open. However, we do make progress and each year there are breakthroughs. People hope to solve it some day - history shows that many open problems in mathematics resisted for long, but they were finally solved after centuries of thinking. "I want it in simple words so it is easy to understand" The definition of P and NP uses things such as "decision problem", "polynomial running time", "nondeterministic" algorithm or Turing machine etc. You need effort to understand them. You have to read about those prerequisites, internalize them in your mind, and only then it will become understandable. "Simple words" won't help in overcoming that. You might have heard lots of intuitive musings about P=NP and are not satisfied. The only cure is rigor. I hope you will not take my words as condescending, but it is not helpful when you say "it makes no sense to me"; it's like someone told you "the program does not work", how are you going to help that person? You need to have a leg to stand on. What you do understand from explanations, what do you not understand from them?
- orionblastar 14y ago
  Most likely I used a poor choice of words, more like I don't understand it. I want to know more, but my knowledge is limited and nobody seems to be able to explain it to me in a way that I can understand. In all honest I don't understand any of it. When I ask about it, instead of explaining it to me, most people just link to the Wikipedia article, instead of using their own words. I've read the Wikipedia article, and I don't understand any of it. My perception is that it does not follow any logic or reason that I understand, there is nothing that I can understand from it, and I don't want to be ignorant on the subject, I want to learn it.
  - sold 14y ago
tptacek 14y ago
Google "ELI5 P=NP".
- orionblastar 14y ago
  It goes to Reddit and I have to sort through comments by trolls on subreddits to try and find any answer that makes sense and is not a joke or a troll comment. I might as well search for the answer on 4Chan, iFunny, or QuickMeme.
  - eurleif 14y ago
    This reddit thread is not at all hard to find: http://www.reddit.com/r/explainlikeimfive/comments/mfswi/eli5_any_of_the_seven_millennium_prize_problems/c30mohh http://www.reddit.com/r/explainlikeimfive/comments/mfswi/eli...
    - alok-g 14y ago
      While an up vote is generally considered to suffice, I cannot thank you enough for this! I get a picture or both P=NP and Peano's axioms from this.
Hkr4294967296 14y ago
A good introduction to the P versus NP problem can be found here: https://www.youtube.com/watch?v=kFl9Z7GPZqg&list=PLODMWBrlhjrZcH3gxm-wKkSdawhp8_ISa https://www.youtube.com/watch?v=kFl9Z7GPZqg&list=PLODMWB...
orionblastar 14y ago
Thanks for all of those who helped or tried to help. I read the Wikipedia, Reddit, Youtube, articles and videos. I find that the Internet is full of misinformation, people with fake degrees and false experts, logical fallacies, bad grammar, poorly written articles that make no logical sense but are passed off as authoritive. I mean I did research before I came here to ask my questions because nothing on the Internet made any logical sense to me, and I failed to understand it. Each one of you has a different explanation, and some of you instead of explaining it keep linking to Wikipedia articles I already read several times and have posted they don't make any sense to me and I don't understand them, continuing to link to them won't help me, explaining them in simpler terms will. I asked Hacker News, because you are supposed to be experts here who can explain anything in simple terms and help people out. I see now that I made a big mistake in that, and I feel like I am being trolled here and been given links to joke sites and misinformation and Wikipedia Word Salads posing as academic journals. I mean I appreciate the efforts, but now I am even more confused than when I first asked my questions. This is why Computer science isn't that popular anymore, and why more people are not studying it as much.
- xwowsersx 14y ago
  I agree that it can sometimes be frustrating to find the right information online, but your absurd pronouncements, e.g. "This is why Computer science isn't that popular anymore, and why more people are not studying it as much." serves only to marginalize you and discourage people from trying to help you out. Again, I understand your frustration, but please consider that certain topics, especially in math and cs, cannot be readily understood without a bit of preparation and that you might just not be grasping what you read because you aren't quite ready. The first answer on this post: https://news.ycombinator.com/item?id=5667089 https://news.ycombinator.com/item?id=5667089 was pretty helpful, what didn't you get about it? To summarize the answer: there are certain problems which are easy to solve and certain problems are seemingly hard to solve but we know are easy to check (if we've arrived at the right solution). P = NP is simply the question, "are the class of problems in NP (the hard ones) actually just as easily solved as the set of P problems or can we prove definitely that there is no efficient algorithm to solve the NP problems?"
- lucozade 14y ago
ronyeh 14y ago
Hi there, Here's how I would describe this to a non-techie. Since you have a tech background, I hope you can use this as a starting point for diving into this interesting, but very deep, question. ================== Is P equal to NP? We built computers to solve tedious problems that we lazy humans don't want to do by hand. Some problems are pretty easy for computers to solve. For example, if you ask a computer to look page by page through a book (e.g., Atlas Shrugged) to search for a particular sentence, it can do it blazingly fast. Even if you double the length of the book, the computer will only have to perform twice as much work (still blazingly fast). We'll call all of these "easy" problems P (think: "easy peasy"). Other problems are a bit harder for our current computers to solve. If we ask a computer to guess my password (20 characters long), it'll take a while before it arrives at the right answer. But if you saw me write down my 20-character password on a post-it, it would be very easy for you (and the computer) to check. All you'd need to do is try to log in! We'll call all of these problems, which are possibly hard to solve, but very easy to check, NP problems. So the question we don't know the answer to: Are all the problems in NP actually solvable in an "easy peasy" way? That is, are the set of all problems in NP just the same as the set of all problems in P? We don't know! And a lot of smart mathematicians are working on the answer. If P=NP, that means "hard problems" are actually "easy problems." This might mean that my computer password would be more easily guessed... and a bunch of other ramifications. ================== This reddit post was linked to earlier: http://www.reddit.com/r/explainlikeimfive/comments/mfswi/eli5_any_of_the_seven_millennium_prize_problems/c30mohh http://www.reddit.com/r/explainlikeimfive/comments/mfswi/eli... I thought it was a pretty good explanation (for me), so I hope you'll give it a chance.
- xwowsersx 14y ago
  Really enjoyed your explanation. Simple and clear.
- jdkanani 14y ago
  Great and simple explanation.
brudgers 14y ago
Some actions take longer than others. When developing sofware, it is sometimes useful to consider the time implications of various alternatives. Sometimes gut feelings are not good enough for those paying the bills or people inclined toward OCD. They want mathematical proof. There is a genus of algorithm called "P" and another genus called "NP". People writing checks and less salty software engineers would like proof that one or the other is faster, or that they are equally fast. They don't have it. Developing a deeper understanding is left as an exercise for the reader who deserves acknowledgement for successfully trolling HN in order to rant about Wikipedia and computer science being unpopular. @Onionblastar: if there is something that is unclear, please do the community the courtesy of telling us what you think it means before complaining.

11 points by orionblastar 14y ago

tlarkworthy 14y ago

Well its not proved so there is no theory, only conjecture. P is polynomial time algorithms, O(n^k) runtime for some k. Algorithms you can run on reasonable sized inputs. NOT O(k^n) exponential time algorithms. Often a hard algorithm like finding the most efficient route through a city, can only be optimally solved by trying every combination of route. Thus, it's runtime is exponential in the number of inputs. However, if there existed a computer that could make lucky guesses, it could just guess the correct route and verify the answer. NP algorithms are Non-deterministic algorithms (guessers) that can solve harder problems in Polynomial time, like combinatorial problems. It is thought P != NP (for obvious reasons) but no-one can prove it. The philosophy of the conjecture is that some algorithms are fundamentally harder than others, but we can't prove it yet.

idupree 14y ago
We know that some algorithms are fundamentally harder than others. Deciding whether two regexps are equivalent requires EXPSPACE which is known to be a strict superset of NP[1]. We just haven't proved whether P != NP. [1] https://en.wikipedia.org/wiki/EXPSPACE https://en.wikipedia.org/wiki/EXPSPACE
- orionblastar 14y ago
  It makes no sense to me. Please explain it in your own words using simplified terms.

idupree 14y ago

Are Wikipedia's explanations clear enough to you? Too long? Too formal or informal? https://en.wikipedia.org/wiki/P_versus_NP_problem https://en.wikipedia.org/wiki/P_versus_NP_problem

orionblastar 14y ago
The Wikipedia article makes no sense to me. Please explain it in simple terms using your own words.
- qbrass 14y ago
  http://simple.wikipedia.org/wiki/P%3DNP http://simple.wikipedia.org/wiki/P%3DNP Try that one.
  - orionblastar 14y ago
    Sorry clear as mud to me. I don't understand that one either.
  - deleted 14y ago
    [deleted]
  - alok-g 14y ago
    Seems like guessing a password would be an example. Assuming that the length of a password is N, if the machine can somehow guess the password, it can verify in O[N]. On the other hand, if the password is not known, the number of possible combinations to try would be exponential.

lacker 14y ago

To understand the P = NP stuff, you first need to understand what people mean by "P" and "NP". "P" refers to problems that can be solved in polynomial time. This includes almost all of the normal algorithms that you use in everyday programming, like sorting a list or using a hash table. "NP" refers to problems whose answers can be checked in polynomial time. This is kind of a weird group of problems. Generally an NP problem will be phrased as, "Can you find a solution to this formula?" Like, can you color a given graph using X colors without giving two adjacent nodes the same color? So. The "P = NP" question is whether these classes of problem are actually the same. You can generally solve a find-the-solution-to-this-formula problem by checking all the possible solutions. That takes exponential time, though. The "P = NP?" question asks, is there a general way of solving these problems faster? Most people who have an opinion suspect that the answer is no. That P is not NP, and that there is no fast way to solve general formulas. However, it's really hard to prove that writing a particular program is impossible, and nobody has proven that P != NP. It's a fairly complicated problem definition, so I wouldn't assume that all these folks are BSing you. It's just tricky to explain because it depends on a lot of other knowledge.

orionblastar 14y ago
How does one learn this other knowledge when they cannot afford tuition at a high priced university anymore but has a university degree, just not a graduate degree?
- tptacek 14y ago
  Wikipedia is a good start here.
  - orionblastar 14y ago
    Wikipedia is not a good start for me because I find the articles there on the subjects involved very confusing. It is like they are writing in bad grammar with poor logic and cannot follow any sort of logic I understand. Anything else to use? Don't get me wrong I used to be big on Wikipedia, but over the years it has gotten worse, using unverified sources, taking things for granted without references and citations, claiming it is 'general knowledge' and does not need verification and citations. Every since 2007 they allowed people with fake degrees to cook the facts and statements in Wikipedia articles and now they are mostly nonsense and poor logic and hard to understand for me. http://www.telegraph.co.uk/news/1544737/Fake-Wikipedia-prof-altered-20000-entries.html http://www.telegraph.co.uk/news/1544737/Fake-Wikipedia-prof-...

rsofaer 14y ago

I didn't understand this sort of math at all until I spent some time in a formal Theory of Computation class studying first finite automata/regular languages, then PDA/CFL and other related topics. I don't think you can expect to understand the reasoning that led to the P=NP question without that kind of study. You must learn the math. On the other hand, here's a short summary of P=NP itself: There is a large group of problems called NP (Non-Deterministic Polynomial), which have been shown to be equivalent, in that a polynomial time algorithm for one could be used to construct polynomial time algorithms for all the others. These problems all have the property that a possible solution can be tested in polynomial time. Because NP is big, many of the problems within it are useful, and it isn't intuitively very far from problems which are soluble in polynomial time, a lot of work has been done on trying to either find polynomial time algorithms for NP, or show that no such algorithm could exist. edit: As lacker mentions, one intuition about NP problems is "Problems for which you must check all the possible solutions and see which one is right."

orionblastar 14y ago
What is polynomial time and Non-Deterministic Polynomial? Please explain these in simple terms.
- rsofaer 14y ago
  NDP is what I said above, you can test a solution in polynomial time. You should get an algorithms textbook to read about time complexity of algorithms if the "Time Complexity" page on wikipedia doesn't make sense to you. I used Cormen's textbook in my algorithms class. This is important, you're going to have trouble if you don't really understand the asymptotic (as the data structure gets large) difference between, for example, searching a list and searching a tree.
  - orionblastar 14y ago
    From my limited understanding a list is a data structure that contains an ordered number of items. For example a linked list that has a pointer to the next item in the data structure that keeps the list in order. A tree data structure has sub-sets of linked nodes starting at a 'root' node, much like a tree. How does time complexity fit into that?

sold 14y ago

This video by Mike Sipser (http://www.youtube.com/watch?v=msp2y_Y5MLE http://www.youtube.com/watch?v=msp2y_Y5MLE) might help you. It might be long, but you need to spend a longer time if you are confused. First of all, P=NP is not a "theory"; it's a _question_. We do not know whether the answer is "yes" or "no"; most experts suspect that the answer is "no", i.e. P is not NP. There were attempts to prove it both ways, none successful or even remotely close. The theory encompassing the question is called computational complexity. It is a relatively new field (foundation is often taken to be ~1965), and many questions are open. However, we do make progress and each year there are breakthroughs. People hope to solve it some day - history shows that many open problems in mathematics resisted for long, but they were finally solved after centuries of thinking. "I want it in simple words so it is easy to understand" The definition of P and NP uses things such as "decision problem", "polynomial running time", "nondeterministic" algorithm or Turing machine etc. You need effort to understand them. You have to read about those prerequisites, internalize them in your mind, and only then it will become understandable. "Simple words" won't help in overcoming that. You might have heard lots of intuitive musings about P=NP and are not satisfied. The only cure is rigor. I hope you will not take my words as condescending, but it is not helpful when you say "it makes no sense to me"; it's like someone told you "the program does not work", how are you going to help that person? You need to have a leg to stand on. What you do understand from explanations, what do you not understand from them?

orionblastar 14y ago
Most likely I used a poor choice of words, more like I don't understand it. I want to know more, but my knowledge is limited and nobody seems to be able to explain it to me in a way that I can understand. In all honest I don't understand any of it. When I ask about it, instead of explaining it to me, most people just link to the Wikipedia article, instead of using their own words. I've read the Wikipedia article, and I don't understand any of it. My perception is that it does not follow any logic or reason that I understand, there is nothing that I can understand from it, and I don't want to be ignorant on the subject, I want to learn it.
- sold 14y ago

tptacek 14y ago

Google "ELI5 P=NP".

orionblastar 14y ago
It goes to Reddit and I have to sort through comments by trolls on subreddits to try and find any answer that makes sense and is not a joke or a troll comment. I might as well search for the answer on 4Chan, iFunny, or QuickMeme.
- eurleif 14y ago
  This reddit thread is not at all hard to find: http://www.reddit.com/r/explainlikeimfive/comments/mfswi/eli5_any_of_the_seven_millennium_prize_problems/c30mohh http://www.reddit.com/r/explainlikeimfive/comments/mfswi/eli...
  - alok-g 14y ago
    While an up vote is generally considered to suffice, I cannot thank you enough for this! I get a picture or both P=NP and Peano's axioms from this.

Hkr4294967296 14y ago

A good introduction to the P versus NP problem can be found here: https://www.youtube.com/watch?v=kFl9Z7GPZqg&list=PLODMWBrlhjrZcH3gxm-wKkSdawhp8_ISa https://www.youtube.com/watch?v=kFl9Z7GPZqg&list=PLODMWB...

orionblastar 14y ago

Thanks for all of those who helped or tried to help. I read the Wikipedia, Reddit, Youtube, articles and videos. I find that the Internet is full of misinformation, people with fake degrees and false experts, logical fallacies, bad grammar, poorly written articles that make no logical sense but are passed off as authoritive. I mean I did research before I came here to ask my questions because nothing on the Internet made any logical sense to me, and I failed to understand it. Each one of you has a different explanation, and some of you instead of explaining it keep linking to Wikipedia articles I already read several times and have posted they don't make any sense to me and I don't understand them, continuing to link to them won't help me, explaining them in simpler terms will. I asked Hacker News, because you are supposed to be experts here who can explain anything in simple terms and help people out. I see now that I made a big mistake in that, and I feel like I am being trolled here and been given links to joke sites and misinformation and Wikipedia Word Salads posing as academic journals. I mean I appreciate the efforts, but now I am even more confused than when I first asked my questions. This is why Computer science isn't that popular anymore, and why more people are not studying it as much.

xwowsersx 14y ago
I agree that it can sometimes be frustrating to find the right information online, but your absurd pronouncements, e.g. "This is why Computer science isn't that popular anymore, and why more people are not studying it as much." serves only to marginalize you and discourage people from trying to help you out. Again, I understand your frustration, but please consider that certain topics, especially in math and cs, cannot be readily understood without a bit of preparation and that you might just not be grasping what you read because you aren't quite ready. The first answer on this post: https://news.ycombinator.com/item?id=5667089 https://news.ycombinator.com/item?id=5667089 was pretty helpful, what didn't you get about it? To summarize the answer: there are certain problems which are easy to solve and certain problems are seemingly hard to solve but we know are easy to check (if we've arrived at the right solution). P = NP is simply the question, "are the class of problems in NP (the hard ones) actually just as easily solved as the set of P problems or can we prove definitely that there is no efficient algorithm to solve the NP problems?"
lucozade 14y ago

ronyeh 14y ago

Hi there, Here's how I would describe this to a non-techie. Since you have a tech background, I hope you can use this as a starting point for diving into this interesting, but very deep, question. ================== Is P equal to NP? We built computers to solve tedious problems that we lazy humans don't want to do by hand. Some problems are pretty easy for computers to solve. For example, if you ask a computer to look page by page through a book (e.g., Atlas Shrugged) to search for a particular sentence, it can do it blazingly fast. Even if you double the length of the book, the computer will only have to perform twice as much work (still blazingly fast). We'll call all of these "easy" problems P (think: "easy peasy"). Other problems are a bit harder for our current computers to solve. If we ask a computer to guess my password (20 characters long), it'll take a while before it arrives at the right answer. But if you saw me write down my 20-character password on a post-it, it would be very easy for you (and the computer) to check. All you'd need to do is try to log in! We'll call all of these problems, which are possibly hard to solve, but very easy to check, NP problems. So the question we don't know the answer to: Are all the problems in NP actually solvable in an "easy peasy" way? That is, are the set of all problems in NP just the same as the set of all problems in P? We don't know! And a lot of smart mathematicians are working on the answer. If P=NP, that means "hard problems" are actually "easy problems." This might mean that my computer password would be more easily guessed... and a bunch of other ramifications. ================== This reddit post was linked to earlier: http://www.reddit.com/r/explainlikeimfive/comments/mfswi/eli5_any_of_the_seven_millennium_prize_problems/c30mohh http://www.reddit.com/r/explainlikeimfive/comments/mfswi/eli... I thought it was a pretty good explanation (for me), so I hope you'll give it a chance.

xwowsersx 14y ago
Really enjoyed your explanation. Simple and clear.
jdkanani 14y ago
Great and simple explanation.

brudgers 14y ago

Some actions take longer than others. When developing sofware, it is sometimes useful to consider the time implications of various alternatives. Sometimes gut feelings are not good enough for those paying the bills or people inclined toward OCD. They want mathematical proof. There is a genus of algorithm called "P" and another genus called "NP". People writing checks and less salty software engineers would like proof that one or the other is faster, or that they are equally fast. They don't have it. Developing a deeper understanding is left as an exercise for the reader who deserves acknowledgement for successfully trolling HN in order to rant about Wikipedia and computer science being unpopular. @Onionblastar: if there is something that is unclear, please do the community the courtesy of telling us what you think it means before complaining.