NP-completeness
/ en-pee com-PLEET /
Inside the vast class NP sit a special few problems that are, in a precise sense, the HARDEST of the whole bunch — and remarkably, they are all tied together: solve any one of them quickly and you have solved them all quickly. These are the NP-complete problems. They are the load-bearing pillars of NP: satisfiability, the travelling salesman decision problem, graph colouring, clique, subset-sum, and thousands more from logistics to biology to chip design. When people say a problem is 'NP-complete', they mean it is both genuinely in NP and as hard as anything in NP can be.
Precisely, a problem L is NP-complete if it satisfies TWO conditions: (1) L is in NP — yes-instances have short, polynomial-time-checkable certificates; and (2) L is NP-hard — every problem in NP reduces to L in polynomial time. The first condition keeps L from being absurdly hard (it is a genuine member of NP, not something undecidable); the second makes it a universal target. Together they pin L at the very top of NP. The astonishing consequence of condition (2) is the all-or-nothing collapse: if even ONE NP-complete problem turned out to be in P, then by reductions EVERY problem in NP would be in P, giving P = NP. Conversely, if P is not NP (as almost everyone believes), then NO NP-complete problem has a polynomial-time algorithm. So all NP-complete problems share a single fate; they stand or fall together. To prove a new problem L is NP-complete you show two things: L is in NP (exhibit the certificate and verifier), and L is NP-hard (reduce a known NP-complete problem, like 3-SAT, to L).
This concept is the most consequential in algorithm design because of what it tells you to DO. Discovering that your problem is NP-complete is not a personal failure or a sign you should try harder; it is a theorem that nobody on Earth has a polynomial-time algorithm for it, and that finding one would be a historic breakthrough (and a million-dollar prize). The honest, practical response is to stop seeking an exact, fast, general algorithm and instead COPE: settle for approximate answers with provable guarantees, restrict to special inputs (small parameters, tree-like structure), use exponential-time methods that are clever enough for the sizes you face, or apply heuristics. One caution to keep honest: 'NP-complete' is a worst-case, asymptotic verdict; many NP-complete problems are routinely solved on real instances by good solvers, because real inputs are not adversarial.
SAT is the original NP-complete problem (Cook-Levin). To show 3-colourability is also NP-complete: (1) it is in NP, since a colouring is a short certificate checkable by scanning edges; (2) it is NP-hard, by a known reduction 3-SAT <=p 3-colouring. Two boxes ticked, so 3-colourability is NP-complete — and shares SAT's fate exactly.
NP-complete = in NP AND NP-hard. One of them in P would put ALL of NP in P (P = NP).
NP-complete is not a proof that the problem needs exponential time — P-vs-NP is open. It means: no known polynomial algorithm, and finding one solves them ALL. Also, the worst-case label does not stop solvers from cracking many real instances; cope, do not give up.