P vs NP and the hardest problems in computer science, explained for kids
Your friend shows you a finished jigsaw puzzle and asks, “Did I do it right?” You can check in a few seconds. Now your friend dumps out a box of 1,000 mixed-up pieces and says, “Your turn.” That takes a LOT longer.
That's the big idea behind NP-Complete problems. Checking an answer is quick. Finding the answer can be so slow that, for big puzzles, even the fastest computer would need longer than the universe has existed.
Computer scientists sort problems into groups. Here are the three you need to know:
Problems a computer can SOLVE quickly, even when they get big. Example: putting a list of names in ABC order.
Problems where you can CHECK an answer quickly. Some are also quick to solve, but for others nobody knows a fast way. Heads up: NP does NOT mean "not P"!
The toughest problems in NP. They are all linked together: find a fast way to solve just ONE of them, and you get a fast way to solve ALL of NP.
Each of these sounds simple. The trouble starts when you want the PERFECT answer for a really big one.
You want to ride your bike to 10 friends' houses and then go home. What is the shortest trip that visits every house? With 3 friends it's easy. With 30 friends it's a nightmare.
Your backpack can only hold 8 pounds. Each thing you could bring has a weight and a fun score. Which things fit in the bag AND give you the most fun?
Color a map so that countries that touch each other never have the same color. Can you do it with only 3 colors? For a small map, you can figure it out. For a huge map, it gets really, really hard.
Your backpack holds 8 pounds. Click things to pack them. Can you get the highest fun score without going over the weight limit?
The secret codes that protect online banking and messages use math puzzles that are easy to check but (we think) super hard to solve. They aren't NP-Complete, but they ARE in NP, so a fast way to solve NP problems would crack them too.
Delivery companies have to pack trucks and plan routes every day. They use clever tricks to find a GOOD answer fast, but they can't be sure it's the BEST answer.
Mathematicians have proven that giant-sized levels of Tetris, Minesweeper, and even Super Mario Bros. are at least as hard as NP-Complete problems!
Here's the question nobody can answer: if an answer is quick to CHECK, is it always quick to FIND, too? In other words, are P and NP really the same group? This is called the P vs NP problem.
Most experts think the answer is “no” (some problems really are hard), but nobody has been able to prove it either way. It's one of 7 famous Millennium Prize Problems, and the Clay Mathematics Institute will pay $1,000,000 to whoever solves it.
If someone proved the answer is “yes” and found a fast trick, the secret codes that protect the internet might stop working. That would be a very big deal!
The smartest mathematicians and computer scientists in the world have been stuck on it for more than 50 years. Maybe you'll be the one to crack it. 🤷