The hardest problems in NP
Some problems in NP are not just hard, they are the hardest in a precise sense. These are the NP complete problems, and they share a remarkable property: an efficient algorithm for any one of them would yield an efficient algorithm for all of them.
Two conditions
A problem is NP complete when it satisfies two requirements.
- It is in NP, so a solution can be verified efficiently.
- It is NP hard, meaning every problem in NP can be transformed into it efficiently.
The second condition makes it a universal target. Solving it solves everything in NP.
How the class was discovered
The first problem shown to be NP complete was boolean satisfiability. Once one such problem existed, others were proven NP complete by reducing satisfiability to them. Today thousands of problems, from the traveling salesman to graph coloring, are known to be NP complete.
Why this matters in practice
If you can show your problem is NP complete, you should stop searching for a fast exact algorithm and instead pursue approximations, heuristics, or special cases. Recognizing NP completeness is a signal to change strategy.
Key idea
NP complete problems are both in NP and NP hard, so they form the hardest core of NP where a fast solution to one would solve them all, and spotting one tells you to seek approximations instead of exact speed.