What is P vs NP
With big O, we saw how much the work grows as the input grows. But for some problems, the number of cases to check explodes when the input grows even a little. That's why no one yet knows a fast way to solve them. The curious thing is that even though finding the answer yourself is hard, checking whether someone else's answer is right is quick.
The number of cases explodes
Say someone has to visit several cities, each exactly once, and wants the shortest route.
With three cities, there are only a few possible orders. But add cities one at a time, and the number of orders to check becomes enormous in the blink of an eye.
Use the button below to add cities.
Add cities and the number of possible visiting orders explodes. (cities +1 → cases multiply)
Each added city multiplies the number of orders. This is the "explosive growth" we saw with big O.
With just a dozen or so cities, there are so many orders that checking them one by one quickly hits a wall.
Hard to solve, easy to check
But here's something interesting. Finding the answer may be hard, but if someone brings you an answer, checking whether it's right is quick.
Think of sudoku. Filling in every blank is a headache, but checking whether a completed grid follows the rules takes just a quick scan.
Press an answer candidate, and checking it is quick. (finding is hard · checking takes a glance)
Hard to find, easy to check: these two coming apart is the mark of such problems.
The traveling salesman problem is the same. Finding the shortest route is hard, but if the question is "is there a route whose total distance is under some amount?", you can confirm it just by adding up the distances of the route someone hands you.
Is there a fast solution?
This raises a big question: "If a problem is quick to check, is it also quick to solve?"
Maybe we just haven't found a clever method yet, or maybe there truly is no fast solution.
Press the two positions below.
Press the two positions. (quick to check = quick to solve? · no one knows yet)
Amazingly, no one knows the answer to this question yet. Mathematicians and scientists around the world have worked on it for a long time, but no one has proven either "there is a fast solution" or "there isn't."
It's the most famous unsolved problem in computer science. So if someone tells you it's easy, a little doubt is fair.
This question goes by the name "P vs NP." The key point is that it's still an unsolved problem.
Hard problems
Problems like this aren't one of a kind. There's the shortest route through many cities, the knapsack of the most valuable items within a weight limit, and coloring a map so neighboring countries never share a color.
They look different on the surface, but underneath they're alike: the number of cases explodes, and checking is easy.
Switch between the examples below.
Press an example to switch. (traveling salesman · knapsack · graph coloring, all the same kind of hard)
Thousands of problems like these have been gathered. Remarkably, if anyone finds a fast way to solve even one of them, all the rest can be solved fast too.
They're holding hands, in a sense, which makes it all the more intriguing: solve one, and you've solved them all.
Summary
In one line: for some problems, the number of cases explodes when the input grows even a little, so no fast solution is known yet.
Yet even when finding the answer is hard, checking it is often easy. So if checking is fast, is solving fast too? That's a big puzzle no one has solved yet.
Press the points below in order to sum up.
Press the key points in order to sum up. (explosion → checking is easy → still unsolved)
Not every problem is equally easy; some are truly tough.
But tough doesn't mean the end. In the next lesson, we'll meet clever methods that give up on the perfect answer and instead quickly find a "good enough" one.