Mathematics
Computational Complexity and the Classes P and NP
Quick fact
No one knows whether P equals NP, but if P = NP, then every problem whose solution can be quickly verified could also be quickly solved—potentially breaking modern encryption and solving countless optimization puzzles instantly.
Why this is interesting
Some problems are easy for a computer to solve, and others seem impossible—even with the fastest supercomputers. What makes a problem 'easy' or 'hard'?
Read the full explanation
Understanding Computational Complexity and the Classes P and NP
Imagine you have a gigantic jigsaw puzzle. Solving it might take hours or days, but checking whether a completed picture is correct takes only seconds. Computers face a similar situation: for many problems, finding the answer is much slower than verifying a proposed answer. Computational complexity is the study of how the time (and other resources) needed to solve a problem grows as the input size grows. Problems that can be solved in 'polynomial time'—like sorting a list or finding the shortest path in a map—are considered 'easy' because the time grows at a manageable rate, such as n² or n³. This class of problems is called P. On the other hand, the class NP contains problems where, if someone hands you a candidate solution, you can check it quickly—again in polynomial time—but finding it might require trying an astronomically large number of possibilities. A classic NP problem is the traveling salesman: given a list of cities and distances, find the shortest route that visits each city exactly once. It's easy to check if a given route is actually a tour and how long it is, but finding the shortest one among all possible tours becomes overwhelming as the number of cities grows.
A deeper explanation
The core of the P vs NP question is whether every problem whose solution can be quickly verified can also be quickly solved. In other words, does P = NP? The classes are defined formally using time complexity. A problem is in P if there exists an algorithm that solves it in time bounded by a polynomial function of the input size (e.g., O(n^2)). A problem is in NP if there exists an algorithm that verifies any proposed solution in polynomial time. This verification algorithm takes the input and a certificate (the proposed solution) and checks it. NP-complete problems are the 'hardest' problems in NP: if any of them can be solved in polynomial time, then every problem in NP can be solved in polynomial time, meaning P = NP. The Cook-Levin theorem (1971) proved that the Boolean satisfiability problem (SAT) is NP-complete, providing the first such problem. Since then, thousands of problems have been shown to be NP-complete, including the traveling salesman, graph coloring, and knapsack problem. The P vs NP problem is a Millennium Prize Problem. Most computer scientists believe P ≠ NP, because decades of effort have failed to find efficient algorithms for NP-complete problems, and their existence would be surprising. However, until a proof is found, the question remains open. Understanding P and NP is essential not just for theoretical computer science but also for fields like cryptography, where security relies on the assumption that certain hard problems are indeed hard to solve.