Are some problems just unsolvable fast?
You saw it with big-O: how work piles up as the input grows. But for some problems, even a tiny bump in input makes the cases to check explode. So nobody knows a fast way to solve them yet. The strange part: finding the answer yourself is hard, but checking whether someone's answer is right is quick.
The cases explode
One person must visit
several cities, each once.
We want the shortest route.
With three cities,
there are only a few orders.
But add cities one by one,
and the number of orders to check
blows up in a blink.
Use the button below to add cities.
Add a city and the number of route orders explodes. (city +1 → cases multiply)
Each time a city is added,
the orders grow by multiplying.
This is the "exploding growth"
you saw in big-O.
With just a dozen-odd cities
the orders are so many
that checking them one by one
hits a wall fast.
Hard to solve, easy to check
But here's the interesting part.
Finding the answer may be hard,
yet if someone brings you one,
checking it is quick.
Think of Sudoku.
Filling every blank is a headache.
But taking a filled-in board
and checking it against the rules
is just a scan with your eyes.
Click an answer candidate and checking is quick. (finding is hard · checking is at a glance)
Hard to find,
easy to check.
Those two pulling apart
is the mark of these problems.
The salesman route is the same.
Finding the shortest one is hard,
but measuring a given route,
"how long is this path in total,"
is just a few additions.
Is there a fast solution?
Here comes the big question.
"If a problem is fast to check,
is it fast to solve too?"
Maybe we just haven't found
the clever method yet.
Or maybe there really is
no fast solution at all.
Click the two sides below.
Click the two sides. (fast to check = fast to solve? · nobody knows yet)
Amazingly, this question
still has no known answer.
Mathematicians and scientists worldwide
have wrestled with it for ages,
but neither "a fast solution exists"
nor "it doesn't" has been proven.
This is the most famous
unsolved problem in computer science.
So if someone says "it's easy,"
you can be a little skeptical.
This question goes by the name "P versus NP." The key point is that it remains an unsolved, open problem.
Some hard problems
These problems aren't just one.
The shortest route over many cities,
picking the most valuable load
within a weight limit, the knapsack,
coloring a map so neighbors
never share a color.
They look different on the surface,
but deep down they're alike.
The cases explode,
and checking is easy.
Switch examples below.
Click to switch examples. (salesman · knapsack · map coloring — all the same kind of hard)
Hundreds of such look-alike
problems are gathered together.
Strangely, if even one of them
gets a fast solution,
all the rest become fast too.
They're holding hands, in a sense.
That makes it even more intriguing.
Crack one and you crack them all.
Wrap-up
Let's gather it in a line.
For some problems, even a small bump
in input makes the cases explode,
so no fast solution is known yet.
Yet finding the answer is hard
while checking is often easy.
So if checking is fast, is solving fast?
That one nobody knows yet,
a big open mystery.
Click through below to wrap up.
Click the key points in order to wrap up. (explosion → easy to check → still open)
Not every problem is equally easy.
Some are genuinely tough.
But tough isn't the end.
In the next story
we'll meet clever ways that
give up on the perfect answer
and quickly find
a "good enough" one instead.