Ask HN: Explain to me the theory behind P=NP in simple words
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?
44 comments
[ 3.4 ms ] story [ 84.7 ms ] threadP 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.
[1] https://en.wikipedia.org/wiki/EXPSPACE
Try that one.
"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.
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-...
This is the book for this topic: http://mitpress.mit.edu/books/introduction-algorithms
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."
How does time complexity fit into that?
The balanced binary tree search operation is an example of something whose cost grows very slowly even as the size of the tree grows rapidly.
There are algorithms that are hard the same way the O(log n) tree is easy: they grow exponentially with the size of input, so very small changes in the input size can drastically increase their cost.
Then if you write down what you think O signifies, you will be at least 3/4 to the answer instead of part way. Nobody can learn for you. Only you can put forth the effort required.
Cowboy up.
Suppose I gave you J(log y) and then told you that you have to solve for it. What does it mean, how do you calculate it, how does it work, cowboy up and do it man!
What do you mean what are the values of J and y? It is math, just do it! Write down what you think J and y signifies. You will be 3/4th the way to the answer instead of part way. Nobody can learn it but you. Only you can put forth the effort.
Search for "Big O notation" on Google.
In this case, the O refers to roughly how complex an algorithm is, or how much time it takes to compute the answer.
n is the size of the input to the problem.
For example, if we are searching for a word through a large Charles Dickens book, we are working on an O(n) problem, where n is the number of pages in the book. We say that this problem has an "order of n" time complexity.
This means that if we double the number of pages in the book to 2 * n, the problem will simply take twice as long. All O(n) problems have this property. If you multiply n by a constant size (e.g., 2), the time it takes to complete the problem will be multiplied by that same constant size.
Some problems are harder. For example, we have two long books, and want to see if there is a sentence in Book 1 that also appears in Book 2. Since you have a tech background, you'll realize that an easy solution to this is to write a for loop nested within a for loop.
This type of problem is O(n^2), because the time it takes to solve the problem scales with the square of the problem size. If I double the number of pages of each book (n), the problem actually takes four times as long!
So this problem is O (order) of n^2 (number of pages).
If you read up on Big O notation, you'll learn that some problems can be solved really fast. We call this O(1) or constant time (since 1 is a constant). For example, if I ask you to tell me if a number is even or odd, you can tell me in constant time, no matter how big an integer I give you (i.e., you just look at the last digit and ignore the rest of the ginormous number).
Some problems are harder.... O(n^3) or even O(n * (n-1) * (n-2) * ... * 3 * 2 * 1).
Good luck!
I would say, "Thank you".
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?
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.
You can't be helped by using "my own words"; my own word for "polynomial" is "polynomial", it is commonly accepted and understood by the computer science community. It can't be dumbed down.
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.
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 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?"
On the plus side, however, I'm sure when you see such an article you'll know straight away that it's the article for you being neither hot nor cold, as it were.
Interestingly, your apparent frustration at not seeing such an article in the (relatively) few that you have read would lead me to suspect that you think that it is quite easy to write such an article. Maybe even as easy as it would be for you to be sure you have found it?
Who knows? Maybe that assertion is correct. Fortunately, it has been noticed that there are a number of similar types of problems i.e. that appear hard to perform but easy to verify. There is also a great deal of interest in the mathematical and computing communities in knowing whether, what many of us consider are hard, are in fact, easy. I would attach a link but I have a feeling you've already seen it.
BTW on the subject of logical fallacies, may I suggest that dismissing all the articles on Wikipedia because of one article in an English daily newspaper, even though it may well have been correct, is a tad rash? There are definitely fallacies and inaccuracies in Wikipedia but there are in English newspapers too. Often remarkably similar fallacies and inaccuracies but I digress.
In fact, Wikipedia had a scandal recently. http://news.cnet.com/8301-1023_3-57514677-93/corruption-in-w...
Not only that but they get some facts wrong and refuse to correct them: http://www.newyorker.com/online/blogs/books/2012/09/an-open-...
I don't really see why Wikipedia is considered a valid source of anything in academia or learning things.
I don't think it is 'easy' to write an article, in fact I know it is hard and difficult without making mistakes and having logical fallacies bad grammar and other things. I was a computer programmer and became sick and disabled and took up writing. I don't have the money to continue my college, so I have to rely on what is on the Internet. But I often find what is on the Internet is either, wrong, has errors, uses logical fallacies, is inaccurate, make nonsense, or leaves things out.
I am starting to find that books are better and more accurate and easier to understand and read than your typical collection of articles at Wikipedia, or posts on Reddit or anywhere else for that matter. The best responses I got on this thread is to read some books that the various computer science courses offer, that is the best advice I can get. Instead of links to stuff I already read or watched and got confused by.
I understand the downvotes, I don't understand something, and since I am questioning one of the main parts of computer science I am seen as a threat and in order to discourage me from asking more questions and drive me from HN, my comments will be downvoted by dupe accounts until I am no longer asking questions or participating here.
I think I have valid questions, valid criticisms, and I am being honest in that I am confused and don't understand it. I am not pretending to be an expert on the subject and faking stuff, I am trying to learn but it is very difficult.
Don't forget that some of the conflicts are going to come about because people are simplifying substantially.
http://web.mit.edu/newsoffice/2009/explainer-pnp.html
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/eli...
I thought it was a pretty good explanation (for me), so I hope you'll give it a chance.
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.