Grokking Algorithms, Second Edition

Appendix B. NP-hard problems

Both the set-covering and traveling salesperson problems have something in common: they are hard to solve. You have to check every possible iteration to find the smallest set cover or the shortest route.

Both of these problems are NP-hard. The terms NP, NP-hard, and NP-complete can cause a lot of confusion. They certainly confused me. In this appendix, I’ll try to explain what all these terms mean, but I need to explain some other concepts first. Here is a roadmap of the things we will learn and how they depend on each other:

But, first, I need to explain what a decision problem is because all the problems we will ...