Ask HN: Explain to me the theory behind P=NP in simple words | Hacker News Reader

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

11 pointsorionblastar43 comments

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?

View on HN

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/eli...

I thought it was a pretty good explanation (for me), so I hope you'll give it a chance.

Really enjoyed your explanation. Simple and clear.

Great and simple explanation.

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.

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?

Wikipedia is a good start here.

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-...

You look up the course website at a decent university, and buy the same textbook they require students read, then read it yourself. Lecture notes and slides can typically be found the same way.

This is the book for this topic: http://mitpress.mit.edu/books/introduction-algorithms

Thank you very much, this is the best advice I could be given here.

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.

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

It makes no sense to me. Please explain it in your own words using simplified terms.

This video by Mike Sipser (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?

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.

You have major gaps in knowledge (for example, in this thread you effectively said you don't know asymptotic analysis of algorithms). Start with something simpler - check what is a polynomial, big O, a Turing machine etc. Backtrack to simple things. Be persistent. Search for a textbook like Cormen's Introduction to Algorithms or Hopcroft/Ullman's Introduction to Automata Theory, and slowly read 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 guess I got books to read then. Thank you.

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."

What is polynomial time and Non-Deterministic Polynomial? Please explain these in simple terms.

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.

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?

The list and the tree don't themselves have time complexity; operations on them do. Finding an element in a list takes O(n) time; in the worst case, you have to check every element of the list. Finding an element in a balanced binary tree takes O(log n) time: at each step, you halve the number nodes you need to check.

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.

What is this "O"? This is what I am talking about, the Wikipedia article and even this thread throw out variables without defining what they are. "O" and "n" what are they, how do I calculate them? How do they work? That is why none of this makes any sense that I can understand.

Well, I tried. Good luck!

Seriously, what is "n" often used to signify in math? Stop thinking of reasons to complain and read for comprehension. Then you will be halfway through O(n).

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.

Most variables in math are unknown until you are given enough information to solve them.

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.

Hi!

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!

Suppose I gave you J(log y)

I would say, "Thank you".

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.

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.

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 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?"

Writing an article on a complex mathematical subject that is sufficiently rigorous, with citations and references, but also sufficiently simple for a layman to understand is hard. In fact, one might even suggest that you may need a very large number of attempts at articles until you find one that meets your exacting needs.

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.

Wikipedia is not accepted as a source by universities. http://library.williams.edu/citing/wikipedia.php http://www.insidehighered.com/news/2007/01/26/wiki http://chronicle.com/blogs/wiredcampus/wikipedia-founder-dis... http://theminaretonline.com/2007/04/19/article1475 http://www.uwgb.edu/dutchs/paperref.htm

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.

Could you quote bits of answers and say what it is that you don't understand about them?

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

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

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

The Wikipedia article makes no sense to me. Please explain it in simple terms using your own words.

http://simple.wikipedia.org/wiki/P%3DNP

Try that one.

Sorry clear as mud to me. I don't understand that one either.

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.

Google "ELI5 P=NP".

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.

This reddit thread is not at all hard to find: http://www.reddit.com/r/explainlikeimfive/comments/mfswi/eli...

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.

Reply on news.ycombinator.com