Every chapter of this course, up until now, has focused on one central question: can a problem be solved at all? The previous chapter delivered a sobering answer for problems like the halting problem, proving that no algorithm can ever exist to solve them, no matter how much time or memory is available. This final chapter shifts the question in a more practical direction. For the enormous number of problems that can be solved, exactly how much time or memory does solving them actually require, and does that requirement grow manageably or explosively as the problem gets larger?
This question turns out to divide the world of solvable problems into two starkly different camps. Some problems can be solved efficiently, with running time that grows reasonably as input size increases. Others, despite being perfectly decidable in principle, seem to require an amount of time that grows so explosively with input size that even the fastest computers imaginable would take longer than the age of the universe to solve moderately large instances. Understanding this divide, and the famous open question sitting at its center, is the subject of this final chapter.
In this tutorial, you will learn how time complexity is measured using Big-O notation, what the complexity classes P, NP, NP-Hard, and NP-Complete mean, how the reduction technique from the previous chapter reappears here in a slightly different role, and why the question of whether P equals NP remains one of the most famous unsolved problems in all of mathematics and computer science.
Before comparing problems to each other, it is necessary to have a consistent way of measuring how much time an algorithm takes. Rather than measuring time in actual seconds, which depends heavily on the specific hardware running the algorithm, complexity theory measures time as a function of input size, counting roughly how many basic steps the algorithm performs as that input size grows.
This relationship is typically expressed using Big-O notation, which describes an upper bound on how an algorithm's running time grows, ignoring constant factors and lower-order terms that become insignificant for large inputs. Big-O notation focuses attention on the shape of the growth curve rather than exact step counts, which is exactly the level of detail needed to meaningfully compare very different algorithms.
| Notation | Growth Description | Example Algorithm |
|---|---|---|
| O(1) | Constant time, unaffected by input size. | Accessing a specific array element by index. |
| O(log n) | Grows very slowly as input size increases. | Binary search on a sorted list. |
| O(n) | Grows directly proportional to input size. | Scanning through a list once from start to end. |
| O(n log n) | Slightly faster growth than linear, common in efficient sorting. | Merge sort or quicksort on average. |
| O(n^2) | Grows proportional to the square of input size. | Comparing every pair of elements in a list. |
| O(2^n) | Grows explosively, doubling with each additional input element. | Checking every possible subset of a set. |
The distinction between the top rows and the bottom row of this table is precisely the dividing line this chapter is building toward. Polynomial growth rates, such as O(n), O(n log n), and O(n^2), remain manageable even for fairly large inputs. Exponential growth rates, such as O(2^n), become utterly impractical remarkably quickly, since doubling the input size can square, or worse, the running time required.
The complexity class P, standing for "polynomial time," consists of every decision problem that can be solved by a deterministic algorithm in time bounded by some polynomial function of the input size, meaning a running time like O(n), O(n^2), or O(n^3), rather than an exponential function like O(2^n).
Problem: Given a list of numbers, sort them into ascending order. Algorithms like merge sort solve this problem in O(n log n) time, which is polynomial in the input size n, so sorting belongs to P.
Problems in P are generally considered "efficiently solvable" or "tractable," since the time required to solve them scales reasonably even as the input grows substantially. Most everyday algorithmic tasks that software engineers deal with, sorting, searching, finding shortest paths in a graph, checking whether a number is prime, all fall neatly within P.
The complexity class NP, standing for "non-deterministic polynomial time," consists of every decision problem for which a proposed solution, sometimes called a certificate or witness, can be verified in polynomial time, even if actually finding that solution from scratch might require far more time than a polynomial amount.
This definition is worth reading twice, since the distinction between finding a solution and verifying a proposed solution is the entire crux of this chapter. NP does not require that a solution can be found quickly; it only requires that, once someone hands you a candidate solution, you can efficiently check whether it is correct.
Problem: Given a set of integers and a target sum T, does some subset of these integers add up exactly to T? Given a specific candidate subset as a proposed solution, verifying it is easy: simply add up the numbers in that subset and check whether the total equals T, a straightforward calculation that takes polynomial time. However, finding such a subset in the first place, without being handed a candidate, appears to require checking an exponential number of possible subsets in the worst case, using currently known algorithms.
Subset sum is a classic example of a problem believed to sit in NP without being known to sit in P, since verification is fast, but no polynomial-time algorithm for actually finding a solution has ever been discovered, despite decades of effort by researchers.
Notice that every problem in P is automatically also in NP, since if a solution can be found in polynomial time, it can certainly also be verified in polynomial time, simply by running the same efficient algorithm. The genuinely open question is whether the reverse containment also holds, whether every problem whose solutions can be efficiently verified can also be efficiently solved from scratch.
Within the vast landscape of NP, some problems turn out to be, in a precise sense, at least as hard as every other problem in NP. This idea is captured by the notion of NP-Hardness, using the reduction technique first introduced in the previous chapter, now applied to compare the difficulty of problems rather than their decidability.
A problem X is called NP-Hard if every problem in NP can be reduced to X in polynomial time, meaning an efficient algorithm for solving X could be used, with only polynomial-time overhead, to solve any problem in NP. Note that an NP-Hard problem is not required to be in NP itself; it might be even harder, requiring more than polynomial time even to verify a proposed solution.
A problem that is both NP-Hard and also a member of NP itself is called NP-Complete. NP-Complete problems represent, in a very real sense, the hardest problems within NP, since solving any single NP-Complete problem efficiently would immediately provide an efficient method for solving every other problem in NP as well, through the chain of polynomial-time reductions connecting them all together.
| Class | Definition |
|---|---|
| P | Problems solvable by a deterministic algorithm in polynomial time. |
| NP | Problems whose proposed solutions can be verified in polynomial time. |
| NP-Hard | Problems at least as hard as every problem in NP, via polynomial-time reduction, though not necessarily in NP themselves. |
| NP-Complete | Problems that are both NP-Hard and members of NP, representing the hardest problems within NP itself. |
Problem (SAT): Given a boolean formula built from variables, AND, OR, and NOT operators, does there exist some assignment of true and false values to the variables that makes the entire formula evaluate to true? The Cook-Levin theorem, a foundational result in complexity theory, proves that SAT is NP-Complete, meaning every single problem in NP can be reduced to SAT in polynomial time. This makes SAT historically significant as the very first problem proven NP-Complete, serving as the starting point from which nearly every other NP-Complete problem known today has since been shown NP-Complete, one reduction at a time.
Just as the previous chapter used reduction to extend a single undecidability result across many other problems, complexity theory uses reduction the same way to extend NP-Completeness across many other problems, without needing to reprove the full Cook-Levin style argument from scratch each time.
To prove a new problem Q is NP-Complete: 1. Show Q is in NP, by demonstrating that a proposed solution to Q can be verified in polynomial time. 2. Show Q is NP-Hard, by demonstrating a polynomial-time reduction from a problem already known to be NP-Complete, such as SAT, into Q. If both conditions hold, Q is NP-Complete.
This exact technique has been used to establish an enormous, well-documented catalog of NP-Complete problems since SAT was first proven NP-Complete, including well-known problems like the traveling salesman problem, the graph coloring problem, and the knapsack problem, each connected back to SAT through a careful chain of reductions.
With all of these definitions in place, the central open question of this entire field can finally be stated precisely: is P equal to NP? In other words, does every problem whose solutions can be efficiently verified also have an efficient algorithm for actually finding those solutions from scratch?
Despite decades of intense research effort, and despite this question being one of the seven Millennium Prize Problems, each carrying a one million dollar reward for a correct solution, nobody has ever proven whether P equals NP or whether P is a strictly smaller class than NP. Most researchers in the field strongly suspect that P does not equal NP, believing that NP-Complete problems like SAT genuinely require exponential time in the worst case, but no one has yet found a way to prove this suspicion beyond doubt.
This unresolved question has enormous practical stakes far beyond pure theory. Much of modern cryptography, for instance, relies on the assumption that certain problems are hard to solve but easy to verify, exactly the NP-style asymmetry discussed throughout this chapter. If P were ever proven equal to NP, with an efficient algorithm actually discovered as part of that proof, it could potentially undermine the security assumptions behind widely used encryption systems.
Recognizing that a problem is NP-Complete carries an important practical lesson for software engineers, even without resolving the P versus NP question. Rather than searching endlessly for an efficient exact algorithm that likely does not exist, engineers facing an NP-Complete problem typically shift strategy, using approximation algorithms that find a good-enough solution quickly, heuristics tailored to the specific structure of their particular instances, or restricting the problem to a smaller, more manageable special case that does admit an efficient solution.
| Mistake | Correct Understanding |
|---|---|
| Assuming NP stands for "not polynomial." | NP stands for "non-deterministic polynomial time," referring to verification time, not an absence of polynomial-time solvability. |
| Believing every problem in NP is automatically NP-Complete. | NP-Complete problems are only the hardest problems within NP; many problems in NP, including everything in P, are not NP-Complete. |
| Confusing NP-Hard with NP-Complete. | An NP-Hard problem does not need to be in NP itself, while an NP-Complete problem must satisfy both being NP-Hard and being a member of NP. |
| Assuming it has been proven that P does not equal NP. | This remains an open question; most researchers suspect P does not equal NP, but no formal proof exists either way. |
Computational complexity shifts the focus of this course from whether a problem can be solved at all to how efficiently it can be solved, dividing decidable problems into classes based on the resources their solutions require. Through Big-O notation, the classes P and NP, and the notions of NP-Hardness and NP-Completeness, this chapter outlined the framework researchers use to reason about tractability, and introduced the P versus NP question, one of the most consequential unsolved problems in all of mathematics.
In this tutorial, you learned how time complexity is measured using Big-O notation, the formal definitions of P and NP with worked examples for each, how NP-Hard and NP-Complete problems relate to one another through reduction, and why the P versus NP question remains unresolved with major practical stakes. This chapter completes the fifteen-part Theory of Computation series on this site, carrying you from the basic mathematical building blocks of sets and languages all the way through automata, grammars, Turing machines, and the outer limits of what computation can and cannot achieve.