ELI5: What does "hard" mean in computer science terms like NP-hard?

In computer science, hard does not mean something is confusing to understand; it means the problem takes an impossibly long time to solve as it gets bigger, because there is no known shortcut.

Imagine planning seating arrangements for a birthday party.

• If you invite just three friends, finding who sits next to whom is easy. You can test a few options in your head in seconds.
• If you invite twenty friends, some of whom are best friends and some who dislike each other, the task explodes. Suddenly, there are quintillions of possible seating charts.

A computer solving this cannot use a magic trick. To find the absolute perfect arrangement, it has to test nearly every single combination one by one. This is what makes a problem NP-hard. Checking if a completed seating chart works takes only a minute, but creating the best one from scratch would take a supercomputer millions of years.

Think of it like a giant ring of thousands of keys and a single locked door.

• Testing one key takes two seconds.


• Checking a key is easy.


• Finding the right key by trying every single one is hard.

In everyday life, a regular "hard" task—like cleaning your entire house—just takes a bit of elbow grease and a couple of hours. But in computer science, a hard problem is like cleaning a house where every speck of dust you find doubles the size of the house. Very quickly, the universe would end before you could finish the chores.

Because these problems are so time-consuming, people and computers usually do not look for the single perfect answer. Instead, they use smart guesses to find an answer that is "good enough" for daily life, like using a map app that finds a very fast route to the grocery store, even if it is not the absolute fastest route on Earth.