Computer Science › Section M · Theory of computation › Topic M.5
Complexity of problems: P and NP
Some problems can be solved in principle but would take longer than the age of the universe. Complexity theory sorts solvable problems by the time they need, and its central question, whether P equals NP, is one of the most famous unsolved problems in mathematics.
Solvable is not the same as practical
"Efficiency and correctness" measured algorithms; complexity theory measures problems. A problem's complexity is that of the best possible algorithm for it. Any one algorithm gives an upper bound: if it solves the problem in \(O(f(n))\) steps in the worst case, the problem is in \(O(f(n))\). A lower bound must hold for every possible algorithm, so it is far harder to prove. Insertion sort puts sorting in \(O(n^2)\), but sorting by comparisons is \(\Theta(n \log n)\), so insertion sort is not optimal. Here n is the input size; for a number, its count of digits or bits.
Polynomial time and the class P
An algorithm runs in polynomial time if its worst-case number of steps is \(O(n^k)\) for some fixed power k. A decision problem has a yes or no answer, and P is the class of decision problems that some algorithm solves in polynomial time. Examples: is this list sorted? Is there a route between two given places in a road network? Is this number prime? That last one was proved to be in P only in 2002. Problems in P are called tractable, because polynomial algorithms are usually practical: \(n^3\) steps for n = 1,000 is a billion, about a second on a modern computer.
Worked example: polynomial against exponential
Assume \(10^9\) steps per second. 1. For n = 20: \(n^3\) takes 8 microseconds and \(2^n\) about a millisecond. 2. For n = 50: \(n^3\) takes 125 microseconds, but \(2^n\) takes about 13 days. 3. For n = 100: \(n^3\) takes 1 millisecond, while \(2^n\) takes about \(4 \times 10^{13}\) years, roughly 3,000 times the age of the universe. 4. Now buy a computer 1,000 times faster. Since \(2^{10} = 1024\), the exponential algorithm handles only about 10 more items in the same time. Check: each extra item doubles \(2^n\), so hardware alone can never rescue an exponential algorithm.
Problems outside P
Some problems are proved to need more than polynomial time. The simplest example is listing every subset of n items: there are \(2^n\) of them, so just writing the output takes exponential time. Some yes or no problems are also proved to need exponential time, such as deciding who wins from a given position in chess played on an n by n board. A solvable problem with no polynomial-time algorithm is called intractable; both examples are proved so. For many other important problems nobody knows: no fast algorithm has been found and none ruled out, though they are often loosely called intractable too.
The class NP
For many hard-looking problems, finding an answer seems slow but checking a proposed one is fast. NP is the class of decision problems with a polynomial-time checker: every yes instance has a certificate, evidence of polynomial size such as a proposed solution, that the checker accepts, and no certificate passes for a no instance. Equivalently, a nondeterministic algorithm, allowed to guess a certificate and then check it, solves any NP problem in polynomial time. NP stands for "nondeterministic polynomial", not "not polynomial". Every problem in P is in NP, since the checker can ignore the certificate and solve the problem directly. So P is contained in NP.
Worked example: checking versus finding
Subset sum asks: does some selection of the given numbers add up exactly to a target? Take 14, 23, 31, 47, 52, 68 and 75, with target 150. 1. Checking: a certificate claims 23, 52 and 75, which add to 150, so the answer is yes, confirmed in two additions. 2. Finding: trying every subset means up to \(2^7 = 128\) of them. 3. With 60 numbers there are \(2^{60} \approx 1.2 \times 10^{18}\) subsets, about 37 years at \(10^9\) per second, yet a check still needs at most 59 additions. 4. For target 200 the answer is no; NP certificates prove yes answers only.
Reductions
A polynomial-time reduction from problem A to problem B is a polynomial-time algorithm that turns every instance of A into an instance of B with the same answer. A fast algorithm for B then gives one for A, so B is at least as hard as A. Example: a Hamilton cycle visits every vertex of a graph once and returns to the start, as in "Euler trails and Hamilton paths" in Discrete Mathematics. The travelling salesperson problem (TSP), as a decision problem, asks whether some tour of all the cities has length at most a budget B. To reduce Hamilton cycle to TSP, give each pair of vertices distance 1 if an edge joins them and 2 if not, and set B = n, the number of vertices.
Worked example: applying the reduction
A graph has vertices A to E and edges AB, BC, CD, DE, EA and AC. 1. Distance 1 for those six pairs, 2 for the other four (AD, BD, BE, CE), and budget B = 5. 2. A tour has five legs of length at least 1, so it fits the budget only if every leg is an edge. 3. The tour A, B, C, D, E, A has length 5, so TSP says yes, and that tour is a Hamilton cycle. 4. Now delete edge DE. E keeps only one edge, so every tour enters or leaves E along a non-edge, giving length at least 6: TSP says no, and there is indeed no Hamilton cycle. Check: the answers match both times.
NP-complete problems
A problem is NP-complete if it is in NP and every problem in NP reduces to it in polynomial time. In 1971 Stephen Cook proved that Boolean satisfiability, deciding whether a logical formula can be made true, is NP-complete; Leonid Levin found the same result independently. In 1972 Richard Karp showed that 21 well-known problems are NP-complete, and thousands are now known, including Hamilton cycle, TSP, subset sum and graph 3-colouring. A polynomial algorithm for any one of them would give one for every NP problem, so P would equal NP. To show a new problem C is NP-complete, show C is in NP and reduce a known NP-complete problem to C, in that direction.
P versus NP: an open question
Does P equal NP? As of 2026 nobody knows. Most computer scientists believe P ≠ NP, but no one has proved it, and in 2000 the Clay Mathematics Institute made it one of its Millennium Prize Problems, with a $1 million prize. Factoring large numbers is in NP, since a claimed factor is checked by one division, but no polynomial-time algorithm for ordinary computers is known, and it is not believed to be NP-complete. Its difficulty is a separate assumption, the one "Public-key cryptography" relies on. In practice, hard problems are tackled with heuristics, approximation algorithms and, for modest sizes, exact search.
Common mistakes to avoid
First, reading NP as "not polynomial"; it means checkable in polynomial time, and it includes all of P. Second, saying NP-complete problems are proved to have no fast algorithm; that is the open question. Third, reversing a reduction: to show C is hard, reduce a known hard problem to C. Fourth, judging a problem by one slow algorithm. Fifth, expecting faster hardware to tame exponential growth. Sixth, calling "find the shortest tour" NP-complete; it is not a yes or no problem, and is called NP-hard.
Key takeaways
A problem's complexity is that of its best algorithm. P, the decision problems solvable in polynomial time, counts as tractable. NP is the class whose yes answers have certificates checkable in polynomial time, and P is contained in NP. A polynomial-time reduction turns instances of A into instances of B with the same answer, making B at least as hard. NP-complete problems, such as satisfiability, TSP and subset sum, are the hardest in NP. Whether P = NP is still open.
Flashcards
Flashcard
The complexity of the best possible algorithm for it
Test your understanding
Question 1 of 5
Which statement correctly describes the class NP?
Question 2 of 5
An algorithm takes 2ⁿ steps and handles 40 items in an hour. On a computer 1,000 times faster, about how many items can it handle in an hour?
Question 3 of 5
Besides showing that a new problem C is in NP, what must you do to prove that C is NP-complete?
Question 4 of 5
What is the status of the P versus NP question, as of 2026?
Question 5 of 5
The Hamilton-cycle-to-TSP reduction is applied to a graph with 4 vertices and edges AB, BC, CD and DA. What TSP question results, and what is its answer?
