NP-complete

NP-complete problems are the hardest problems in NP, and they form a remarkable brotherhood: a fast algorithm for ANY ONE of them would instantly give a fast algorithm for ALL of them, and indeed for everything in NP. They are all polynomial-time interreducible, so in a precise sense they are the same problem wearing different costumes: SAT, clique, colouring, scheduling, tours. Solve one efficiently and the whole edifice falls.

A problem is NP-complete if it satisfies two conditions at once. First, it is IN NP: its yes-answers have short, polynomial-time-checkable certificates. Second, it is NP-HARD: every problem in NP polynomial-time reduces to it. The first condition keeps it from being too hard to verify; the second makes it as hard as anything in NP. Together they pin it to the exact top of NP. Because every NP-complete problem reduces to every other (each is in NP, so reduces to any NP-hard problem), they are all equivalent up to polynomial-time translation, which is why a single breakthrough would propagate everywhere.

This is the dramatic payoff of the theory. If even one NP-complete problem turned out to be in P, then P = NP and thousands of important problems would become tractable at a stroke; conversely, if any one of them is proven to need super-polynomial time, then P is not equal to NP and none of them has a fast algorithm. The Cook-Levin theorem gave us the first NP-complete problem, SAT, and Karp and others then reached a vast toolkit by chains of reductions. When you prove your own problem NP-complete, you simultaneously show it is in NP (exhibit a verifier) and that a known NP-complete problem reduces to it.