- Unsupervised Learning
- Posts
- P vs. NP Explained
P vs. NP Explained
If you spend time in or around the programming community you probably hear the term “P versus NP” rather frequently. Unfortunately, even many with formal computer science training have a weak understanding of the concept.
So here’s a simple and concise explanation:
So let’s figure out what we mean by P and NP.
P problems are easily solved by computers, and NP problems are not easily solvable, but if you present a potential solution it’s easy to verify whether it’s correct or not.
As you can see from the diagram above, all P problems are NP problems. That is, if it’s easy for the computer to solve, it’s easy to verify the solution. So the P vs NP problem is just asking if these two problem types are the same, or if they are different, i.e. that there are some problems that are easily verified but not easily solved.
It currently appears that P ≠ NP, meaning we have plenty of examples of problems that we can quickly verify potential answers to, but that we can’t solve quickly. Let’s look at a few examples:
A traveling salesman wants to visit 100 different cities by driving, starting and ending his trip at home. He has a limited supply of gasoline, so he can only drive a total of 10,000 kilometers. He wants to know if he can visit all of the cities without running out of gasoline. (from Wikipedia)
A farmer wants to take 100 watermelons of different masses to the market. She needs to pack the watermelons into boxes. Each box can only hold 20 kilograms without breaking. The farmer needs to know if 10 boxes will be enough for her to carry all 100 watermelons to market. (from Wikipedia)
All of these problems share a common characteristic that is the key to understanding the intrigue of P versus NP: In order to solve them you have to try all combinations.
This is why the answer to the P vs. NP problem is so interesting to people. If anyone were able to show that P is equal to NP, it would make difficult real-world problems trivial for computers.
P vs. NP deals with the gap between computers being able to quickly solve problems vs. just being able to test proposed solutions for correctness.
As such, the P vs. NP problem is the search for a way to solve problems that require the trying of millions, billions, or trillions of combinations without actually having to try each one.
Solving this problem would have profound effects on computing, and therefore on our society.
Feb 7, 2017 — Added Wikipedia attributions.March 2, 2014 — Cleaned up some of the explanation to avoid confusion.
There is a class of NP problems that are NP-Complete, which means that if you solve them then you can use the same method to solve any other NP problem quickly.
This is a highly simplified explanation designed to acquaint people with the concept. For a more complete exploration, check out the Wikipedia article or the numerous resources online.