Eli5: what are P and NP problems and how we are using it in real life?
In: Mathematics
I have a deck of cards with some cards missing. How many steps would it take you to determine whether the King of Spades is missing? If the king is missing, you need to look at all remaining cards to be sure. If the king _isn’t_ missing, you will need to look at half the deck (on average) before you run into it and can say it’s not missing.
Now, imagine If the deck was twice as big (because the numbers go 2—23 instead of 2—10). You’d need twice as many steps to determine whether the king of spades is missing. If it were half as big, you’d need half as many steps too. The average number of steps is always proportional to the size of the deck.
Now, imagine you know for a fact that the deck is sorted. You can just look at the last eight cards (presumably, the kings and aces) to see if the king of spades is in there. Doesn’t matter if you double the size or multiply it a hundredfold, it’ll always only ever take you at most eight steps to check if that particular card is missing.
Algorithmic Complexity is an area of computer science that studies this idea of how much work it takes to solve a problem as you change the size of the input data. One of the more interesting things they study is the big categories of problems that have similar complexity (that is: the number of steps grows in the same rough shape).
Which brings us to P and NP. P is the category of problems for which you can find a solution fairly efficiently (for a very specific, technical definition of “efficiently”). NP is the category of problems for which you might or might not be able to find a solution efficiently yourself, but, if I give you a solution, you can efficiently check if that solution is correct. (You might notice that all P problems are also NP problems, because you can just build your own solution to verify that my solution is correct).
The important question that we don’t have an answer to is: are there any NP problems that aren’t also P problems (P ≠ NP), or are all NP problems efficiently solvable (P = NP)? It’s more or less accepted that P ≠ NP, but we don’t know that for a fact (and some prominent computer scientists aren’t really sure it’s actually true).
One way this idea is used in practice is cryptography. E.g. multiplying two big prime numbers is P, but finding those numbers given the result is NP. We can take advantage of this difference to build so-called asymmetric encryption schemes — a setup where I have two keys (one public and one private), and anybody can use the public key to encrypt messages that can only be decrypted with the private key. This is one of the fundamental parts of how we keep the internet secure.
Latest Answers