Ask HN: Explain P != NP in plain english Could someone explain P != NP to me like I'm literally five :-) What is P? What is NP? Why and what part of it is nondeterministic and deterministic? How does verification play into it? Does this only apply to decision (yes/no) problems or can it be other problems? What does an equal to and not equal to relationship mean? Why does it matter? Also what is NP-Hard? What is NP-Complete? Thank you! |
“When you ask your question, display the fact that you have done these things first; this will help establish that you're not being a lazy sponge and wasting people's time. Better yet, display what you have learned from doing these things. We like answering questions for people who have demonstrated they can learn from the answers.”
Also, knowing what you know and don’t know may make helping you a lot easier, thus increasing the possibility that you’ll get an answer that helps you.
In particular, if you did “Try to find an answer by searching the Web.”, did you find https://en.wikipedia.org/wiki/P_versus_NP_problem? If so, what’s insufficient for you in that?
(I also think http://www.catb.org/~esr/faqs/smart-questions.html#forum applies. IMO, this isn’t the forum to ask these kind of question, but will let the community judge that)
I read through the wikipedia but it didn't really click with me and I felt it definitely wasn't written for a five year old :-)
In my defence I wanted to hear how others would state the problem and was afraid of biasing the response by leading too much with what I may or may not correctly know. Though I had tried to provide some direction with my questions that I hoped would be addressed by others.
I thought the question was in line with the general HN guidelines of "anything that gratifies one's intellectual curiosity".
P is the set of problems which grow as some polynomial in the degree of the problem. We say that it takes polynomial time to solve them.
Looking at our matrices - if it takes 5цs to multiply a 2x2 matrix, it will take 4 timrs as long to multiply a 4x4 matrix, and so on.
A three dimensional matrix multiplication grows as the cube - a 4x4x4 matrix takes eight times as long as a 2x2x2 matrix.
These problems belong to the class of problems which can be solved in polynomial time. This class is called P.
Now look at the travelling salesman problem. Here we have to visit each town on a map using the minimum distance travelled. With two towns this is easy. Add a third and you have to compare distances between each pair of towns - a total of three comparisons. Add a fourth town and you are at 24 comparisons. Five towns makes 120 comparisons. The problem grows faster than a square, faster than a cube, faster than any polynomial. The approximation is exponential.
These problems belong to the set NP, those for which we know no better solution than evaluating each alternative in a time which is exponential.
The Non-deterministic part of NP comes because if we were given an oracle, that magically gave us the solution, it would be really easy to verify that the solution is correct.
The fascinating part is that we cannot prove that the two sets are not the same. Maybe Terence Yao will devise an algorithm next year which solve the travelling salesman (Tp) in polynomial time.
The reason we (and he) do not believe this is that there are problems which are so hard, that if we can solve one of them in polynomial time, we can solve every problem in NP in polynomial time. TP is one of these. We call such problems NP-complete.
Finally, any problem for which we do not know a polynomial time solution is NP hard. These problems,