What's the need for creating problems as NP and P?

What's the main intention or main use of splitting any problem to NP and P? Is there is any historical reason for this or have they created these concepts to help us? If so, where can 开发者_Python百科these help us?

---

This is far too complex of a question to expect a thorough answer here, but in short, from a practical perspective, problems in P are those for which a solution can be found in a reasonable amount of time and problems in NP are those for which a solution would take too much time to compute (assuming P != NP).

The boundary between P and NP can be informally thought of as the boundary between problems which can and can't efficiently be solved using computation.

You should start by reading wikipedia http://en.wikipedia.org/wiki/P_versus_NP_problem to learn more about the motivation and purposes of these complexity classes.

---

I think the "practical" intention of splitting problems to P and NP is the lower bound. If you prove that a problem is NP-hard (and you agree with the common belief that P != NP), you've proved you can't find an algorithm for the problem that runs in a reasonable amount of time.

More informally, say your boss asks you to write an algorithm that runs in 5min. If you say you can't find one, he'll think you're slacking off. If you show him what he asked you is NP-hard, he should be convinced you can't do it.. Returning to formalism, you can then justify using an approximation algorithm.

This is all a historical conversation because now, in the industry, we sometimes implement problems that are NP-complete (for example SAT-solvers) or even PSPACE-complete (for example formal verification, which is PSPACE-complete in the size of the formula). On the other hand, for example in graphics, you sometimes can't implement an algorithm which runs in n^2. Even nlogn can sometimes be edgy.

---

The main idea is to segregate problems based on the level of difficulty.

Here the P would refer to all the easy problems(solvable in a reasonable amount of time). And NP the difficult ones. (No reasonable time solution exists but, if you can guess the solution, it can be verified quickly)

Once you have categorised problems into these two sets then you can worry about solving.

If for instance, you do come across a NP problem, instead of breaking your head over the solution, you can realise that it is unsolvable in a reasonable amount of time and move on (or use good guess-work and check the solutions).

On the other hand, if it is a P problem, then you could worry about finding a more efficient solution and so on.