An NP-complete problem is one of the hardest problems in the class NP, in a precise technical sense: every other problem in NP can be transformed into it efficiently, so a fast algorithm for one NP-complete problem would immediately give a fast algorithm for all of them. This makes the NP-complete problems a single linked fate - they all stand or fall together on the P vs NP question.
The concept comes from Stephen Cook’s 1971 paper “The Complexity of Theorem-Proving Procedures.” Cook showed that any problem recognizable by a polynomial-time-bounded nondeterministic Turing machine can be reduced to the problem of deciding whether a propositional formula is satisfiable. That made satisfiability (SAT) the first problem proved to be NP-complete - the result now known as the Cook-Levin theorem, since Leonid Levin reached a similar conclusion independently.
The Stanford Encyclopedia of Philosophy explains the practical weight of this idea: a great many natural and useful computational problems turn out to be NP-complete, and none of them is known to have any algorithm faster than exponential time. Because they are all interreducible, finding one efficient algorithm would collapse the whole class to easy.
Shortly after Cook’s paper, Richard Karp showed that twenty-one well-known combinatorial problems are also NP-complete, demonstrating that NP-completeness was not a curiosity confined to logic but a pervasive feature of practical computation. Today thousands of problems across scheduling, routing, and optimization are known to be NP-complete.