Mathematics
The Complexity Classes NP and NP-Complete Problems
Quick fact
The first problem ever proven NP-complete was the Boolean satisfiability problem (SAT), shown by Stephen Cook in 1971. This single result unlocked the entire class of NP-complete problems, and today thousands of problems, from scheduling to protein folding, are known to be NP-complete.
Why this is interesting
You’ve probably heard of the traveling salesman problem. But why is it so hard that even the smartest computers struggle with it? The answer lies in a mysterious class called NP.
Read the full explanation
Understanding The Complexity Classes NP and NP-Complete Problems
Imagine you’re given a huge jigsaw puzzle. Finding the solution might take forever, but if someone hands you the completed puzzle, you can quickly check if it’s correct. This is the essence of NP: problems where a solution can be verified quickly (in polynomial time). NP stands for 'nondeterministic polynomial time', but don’t let the name confuse you—it just means 'verifiable in polynomial time'. Now, some problems in NP are so hard that they capture the difficulty of the entire class. These are called NP-complete. They are the 'hardest' problems in NP: if you found a fast way to solve any one of them, you could solve every problem in NP just as fast. The traveling salesman problem is a classic example: given a list of cities and distances, find the shortest possible route that visits each city exactly once and returns to the start. No one knows a fast (polynomial-time) algorithm for it, but if someone gives you a candidate route, you can quickly add up the distances and check if it’s shorter than the best known. The big question—called P vs NP—asks whether every problem whose solution can be quickly verified can also be quickly solved. If P=NP, then every NP problem (including all NP-complete ones) has a fast solution. If P≠NP, some problems will forever be intractable.
A deeper explanation
The formal definition of NP relies on a verifier: a polynomial-time algorithm that, given an instance and a certificate (a proposed solution), can confirm or reject the certificate. A problem is in NP if for every 'yes' instance there exists a certificate that the verifier accepts, and for every 'no' instance no certificate is accepted. NP-complete problems are defined using polynomial-time reductions. A reduction from problem A to problem B is an algorithm that transforms any instance of A into an instance of B in polynomial time, preserving the answer. If such a reduction exists, A is 'no harder' than B. A problem is NP-complete if it is in NP and every problem in NP can be reduced to it in polynomial time. This means that a polynomial-time algorithm for any NP-complete problem would solve every NP problem—that is, P=NP. Why does this matter? Many real-world problems in optimization, scheduling, circuit design, and logistics are NP-complete. If P=NP, we could solve them optimally and efficiently, revolutionising fields like cryptography, AI, and operations research. But most researchers believe P≠NP, which is why we rely on heuristics and approximations for these hard problems. The first NP-complete problem was Boolean satisfiability (SAT), proven by Stephen Cook (and independently by Leonid Levin). Since then, thousands of problems have been shown NP-complete by reducing SAT (or another known NP-complete problem) to them. This web of reductions shows that all NP-complete problems are essentially the same problem in disguise—each one encapsulates the full difficulty of NP.