Grokking Algorithms

Chapter 8
 
 
I
 
 
Greedy algorithms
How do you tell if a problem is NP-complete?
Jonah is picking players for his fantasy football team. He has a list of 
abilities he wants: good quarterback, good running back, good in rain, 
good under pressure, and so on. He has a list of players, where each 
player fulfills some abilities.
Jonah needs a team that fulfills all his abilities, and the team size 
is limited. “Wait a second,” Jonah realizes. “This is a set-covering 
problem!”
Jonah can use the same approximation algorithm to create his team:
1. Find the player who fulfills the most abilities that haven’t been 
fulfilled yet. 
2. Repeat until the team fulfills all abilities (or you run out of space
on the team).
NP-complete problems show up everywhere! It’s nice to know if the 
problem you’re trying to solve is NP-complete. At that point, you can 
stop trying to solve it perfectly, and solve it using an approximation 
algorithm instead. But it’s hard to tell if a problem you’re working on is 
NP-complete. Usually there’s a very small difference between a problem 
that’s easy to solve and an NP-complete problem. For example, in the 
previous chapters, I talked a lot about shortest paths. You know how to 
calculate the shortest way to get from point A to point B.

---

159
NP-complete problems
But if you want to find the shortest path that connects several points, 
that’s the traveling-salesperson problem, which is NP-complete. The 
short answer: there’s no easy way to tell if the problem you’re working 
on is NP-complete. Here are some giveaways:
• Your algorithm runs quickly with a handful of items but really slows 
down with more items.
• “All combinations of X” usually point to an NP-complete problem.
• Do you have to calculate “every possible version” of X because you 
can’t break it down into smaller sub-problems? Might be
NP-complete.
• If your problem involves a sequence (such as a sequence of cities, like 
traveling salesperson), and it’s hard to solve, it might be NP-complete.
• If your problem involves a set (like a set of radio stations) and it’s hard 
to solve, it might be NP-complete.
• Can you restate your problem as the set-covering problem or the 
traveling-salesperson problem? Then your problem is definitely
NP-complete.