Eli5: what are P and NP problems and how we are using it in real life?
In: Mathematics
Roughly:
A “P” problem is one that can be solved “quickly” in a very specific technical sense.
An example is “sort these numbers”.
An “NP” problem is one where we can check a proposed solution quickly (in that same very specific technical sense).
Intuitively, you’d expect that it might be harder to solve problems than to check their solutions. For example, if I give you pen and paper and say: “Find a seven-digit prime factor of 21398004009749.” you know you might need a lot of time. But if I say “Check that 8934773 is a seven-digit factor of 21398004009749” you know you’ll be done within a few minutes.
~~It turns out that factorising numbers is in P (even though it seems obviously slower than checking factors). The quick algorithm is unintuitive and leans on some pretty advanced mathematics, but it is fast in the technical sense used here.~~ This is wrong. We don’t know if factorisation is in P. See replies below.
However, there are some NP problems that might or might not be in P.
An example is
“Here are some cities, joined by highways. Find a route along highways only that visits each city exactly once”.
The best *known* methods for solving that problem either:
* Are very very slow, as the number of cities gets large, or
* Have a probability (ever so small) of failing, or
* Only work for some special arrangements of cities, not all.
There might be some special, super-tricky algorithm nobody has yet thought of that solves this problem quickly. We don’t know yet. So we don’t know if this problem is in P.
On the other hand, it’s trivially easy to solve *this* problem:
“Here are some cities, joined by highways. Here’s a route through the cities. Check that it goes along highways only, and visits each city exactly once”.
So the problem is in NP. It’s quick to *check* a proposed solution.
There are lots of problems like this. Another example is related to the game “battleships”.
“I give you an empty grid and some battleships. Can you place all the battleships on the grid so that no two battleships are next to each other?”
Nobody knows a quick way to solve this. On the other had, it’s easy to check a solution:
“I give you an empty grid and some battleships. Here is a proposed arrangement of battleships. Have all the battleships been placed on the grid so that no two battleships are next to each other?”
So this puzzle is NP, but may or may not be P.
The P vs NP problem is the question “Are there any NP problems that are *not* P?” Nobody knows the answer to this. If the answer is “yes” then it turns out that planning trucking routes or placing battleships on a grid are intrinsically difficult problems, and we will always have to rely on approximations and shortcuts. If the answer is “no” then it turns out that every problem that can be quickly checked can also be quickly solved (perhaps not *as* quickly, but “quickly” in the technical sense that’s relevant here).
Latest Answers