Introduction

Computational complexity theory asks a simple question in a precise way:

How much computational resource is needed to solve a problem?

The word resource is deliberately broad. The most familiar resource is time: how many elementary steps an algorithm uses before it returns an answer. Another central resource is space: how much memory it uses while computing. Later in this book we will also study randomness, communication, circuit size, proof length, quantum operations, and other resources. Complexity theory is the part of theoretical computer science that organizes these questions into a mathematical theory.

At first sight, this may sound like ordinary algorithm analysis. If you have studied algorithms, you have already compared procedures by running time: binary search is faster than linear search on a sorted array; merge sort runs in \(O(n \log n)\) time; Dijkstra’s algorithm solves shortest paths efficiently when edge weights are nonnegative. Complexity theory begins there, but it changes the level of the question.

Algorithm analysis often asks:

How efficient is this particular algorithm?

Complexity theory asks:

How efficient can any algorithm possibly be for this problem?

That shift is profound. It turns computer science from the design of clever procedures into the study of inherent computational difficulty.

For example, consider the problem SAT, short for Boolean satisfiability. An input is a Boolean formula, built from variables such as \(x_1,x_2,\dots,x_n\), logical connectives such as AND, OR, and NOT, and parentheses. The question is whether there is an assignment of true/false values to the variables that makes the formula true. For instance,

\[ (x_1 \lor x_2) \land (\lnot x_1 \lor x_3) \]

is satisfiable: take \(x_1=\text{true}\), \(x_2=\text{false}\), and \(x_3=\text{true}\). But the formula

\[ x_1 \land \lnot x_1 \]

is not satisfiable.

A direct brute-force algorithm tries all \(2^n\) truth assignments. That is correct, but usually too slow when \(n\) is large. The complexity-theoretic question is not merely whether this brute-force algorithm can be improved. It is whether SAT has any polynomial-time algorithm at all. The Cook–Levin theorem showed that SAT is complete for the class NP, and Karp soon showed that many natural combinatorial problems are complete for NP under polynomial-time reductions [Cook 1971; Karp 1972]. This is one of the central reasons SAT appears throughout this book.

From computability to complexity

Before we ask how many steps computation requires, we need a mathematical notion of computation itself. A model of computation is an idealized machine or formal system that defines what it means to compute. The most famous such model is the Turing machine, introduced by Alan Turing in his analysis of effective computation [Turing 1936]. A Turing machine has a finite control, an unbounded tape divided into cells, and a head that reads and writes symbols while moving left or right.

The important point is not that real computers look like Turing machines. They do not. The important point is that Turing machines give a clean mathematical model of step-by-step symbolic computation. They let us prove theorems about algorithms without depending on a particular processor, programming language, or hardware generation.

The first great distinction is between computable and uncomputable problems.

A problem is computable if there exists an algorithm that always gives the correct answer and eventually halts. For example, given two integers, computing their greatest common divisor is computable; Euclid’s algorithm solves it. By contrast, the Halting Problem—given a description of a program and an input, decide whether the program eventually halts—is not computable in full generality, as Turing proved [Turing 1936].

Complexity theory usually begins after computability has been settled. It asks a more refined question:

Among the computable problems, which ones are feasible, and which ones are computable only with enormous resource requirements?

This is why complexity theory is not the same as computability theory. Computability theory separates the possible from the impossible. Complexity theory studies the cost of the possible.

Input size and scalability

To measure computational cost, we need to say what grows. The standard answer is the input size.

If the input is a binary string \(x\), its size is its length, written \(|x|\). If the input is a graph, its size may be the number of bits needed to encode the graph, or a pair such as the number of vertices and edges. If the input is an integer \(N\), its size is not \(N\) itself but approximately \(\log_2 N\), because that is how many bits are needed to write \(N\) in binary.

This last point is easy to overlook. Suppose an algorithm tests all numbers from \(1\) to \(N\). Its running time is roughly \(N\). But if the input is the binary representation of \(N\), and the input length is \(n \approx \log_2 N\), then \(N \approx 2^n\). So the algorithm is exponential in the input length. Complexity theory measures scalability with respect to representation size, not with respect to the numerical value that happens to be represented.

This is why encodings matter. An encoding is a way to represent mathematical objects as strings over a finite alphabet, usually binary strings. A graph, formula, integer, matrix, or proof must be encoded before a machine can process it. Reasonable encodings usually differ by at most polynomial factors, but unreasonable encodings can distort complexity. Chapter 3 will treat this carefully.

Efficient computation and polynomial time

Complexity theory needs a robust mathematical meaning for the phrase “efficient algorithm.” The standard class is P, the class of decision problems solvable by a deterministic algorithm in polynomial time.

A decision problem is a problem with a yes/no answer. For example:

• Given a graph \(G\) and vertices \(s,t\), is there a path from \(s\) to \(t\)?
• Given a Boolean formula \(\varphi\), is \(\varphi\) satisfiable?
• Given integers \(a,b,c\), is \(a \cdot b = c\)?

A running time is polynomial if it is bounded by \(n^k\) for some constant \(k\), where \(n\) is the input length. Thus \(n^2\), \(n^5\), and \(17n^3+4n+9\) are polynomial bounds. By contrast, \(2^n\), \(n!\), and \(2^{\sqrt n}\) are not polynomial bounds.

The idea that polynomial time captures a broad mathematical notion of feasible computation is often associated with the Cobham–Edmonds thesis. Cobham proposed polynomial time as a machine-independent notion of computational feasibility, and Edmonds emphasized polynomial-time algorithms as “good” algorithms in the context of combinatorial optimization [Cobham 1965; Edmonds 1965]. This is not a theorem about the physical world. It is a guiding convention: polynomial time is stable under changes among many reasonable machine models, closed under composition, and mathematically tractable.

The convention is not perfect. An \(n^{100}\)-time algorithm is polynomial but not practical for any realistic input size. A \(1.0001^n\)-time algorithm is exponential but might be useful for moderate \(n\). Complexity theory does not claim that polynomial time exactly equals practical efficiency in every engineering situation. Rather, polynomial time is a robust first approximation to scalable computation.

For example, graph reachability—given a directed graph and two vertices \(s,t\), decide whether \(t\) is reachable from \(s\)—has simple polynomial-time algorithms such as breadth-first search or depth-first search. If the graph has \(m\) edges and \(n\) vertices, these algorithms run in time \(O(n+m)\) under standard adjacency-list representations. SAT, on the other hand, has no known polynomial-time algorithm, and the existence of one would imply polynomial-time algorithms for every problem in NP.

Problems, languages, and instances

Complexity theory often represents decision problems as languages. A language is simply a set of strings. If we fix an encoding scheme, the set of all yes-instances of a decision problem becomes a language.

For example, let

\[ \textsf{SAT} = \{\langle \varphi \rangle : \varphi \text{ is a satisfiable Boolean formula}\}. \]

Here \(\langle \varphi \rangle\) denotes an encoding of the formula \(\varphi\) as a string. The language \(\textsf{SAT}\) contains exactly those encodings whose formulas are satisfiable.

This language viewpoint may feel abstract at first, but it is extremely useful. It lets us compare problems using set membership:

\[ x \in L \]

means that the input string \(x\) is a yes-instance of the language \(L\). A decision algorithm for \(L\) must accept strings in \(L\) and reject strings not in \(L\).

For example, define

\[ \textsf{PATH}=\{\langle G,s,t\rangle : \text{there is a path from }s\text{ to }t\text{ in }G\}. \]

Then solving the graph reachability decision problem is the same as deciding membership in \(\textsf{PATH}\).

Many natural computational tasks are not yes/no tasks. Sorting, factoring, finding a shortest path, and producing an optimal schedule are search problems or function problems. Complexity theory studies these too, but decision problems are the cleanest starting point. In many settings, a search problem can be related to an associated decision problem. For example, the question “What is the length of the shortest path from \(s\) to \(t\)?” can be studied through decision questions such as “Is there a path from \(s\) to \(t\) of length at most \(k\)?”

Hardness, reductions, and completeness

One of the deepest ideas in complexity theory is that we can compare problems without solving them directly. The main tool is a reduction.

Informally, a reduction from problem \(A\) to problem \(B\) is an efficient method for transforming any instance of \(A\) into an instance of \(B\), so that solving the transformed instance of \(B\) solves the original instance of \(A\).

If \(A\) reduces to \(B\), then \(B\) is at least as hard as \(A\), relative to the chosen type of reduction. If we had an efficient algorithm for \(B\), we could combine it with the reduction to get an efficient algorithm for \(A\).

Here is a simple example. Suppose \(A\) is the problem of deciding whether a graph has a triangle, and \(B\) is the problem of deciding whether a graph has a clique of size \(3\). These are essentially the same problem, because a triangle is exactly a clique of size \(3\). The reduction maps an input graph \(G\) for triangle detection to the pair \((G,3)\) for clique detection. A solver for \(B\) immediately solves \(A\).

More interesting reductions transform problems that look very different. Karp’s 1972 work showed that many natural problems—such as CLIQUE, VERTEX COVER, and HAMILTONIAN CYCLE—are NP-complete by reductions from SAT and related problems [Karp 1972]. These reductions explain why the same kind of difficulty appears across logic, graphs, scheduling, packing, and combinatorial search.

A problem is hard for a class if every problem in the class reduces to it. A problem is complete for a class if it is both hard for the class and belongs to the class. Completeness is a way of finding representative hardest problems. SAT is NP-complete: it belongs to NP, and every problem in NP can be reduced to SAT by a polynomial-time reduction [Cook 1971].

Completeness is not merely a classification label. It is a method of transferring knowledge. If any NP-complete problem has a polynomial-time algorithm, then every problem in NP has a polynomial-time algorithm. Conversely, if any problem in NP is proved not to have a polynomial-time algorithm, then no NP-complete problem has one.

The meaning of NP

The class NP is often misunderstood. It does not mean “not polynomial.” It stands for nondeterministic polynomial time, but one of its most useful definitions is in terms of certificates.

A decision problem is in NP if every yes-instance has a certificate whose correctness can be verified in polynomial time.

A certificate is extra information that helps convince us that the answer is yes. A verifier is an algorithm that checks the certificate.

For SAT, a certificate is a satisfying assignment. Given the formula and the assignment, the verifier simply evaluates the formula. If the formula has length \(n\), this can be done in time polynomial in \(n\).

For HAMILTONIAN CYCLE, the input is a graph, and the question is whether the graph has a cycle that visits every vertex exactly once and returns to the start. A certificate is the proposed ordering of the vertices in such a cycle. The verifier checks that each vertex appears exactly once and that all required edges exist.

This is the key distinction:

• Finding a certificate may be hard.
• Checking a proposed certificate may be easy.

The P versus NP problem asks whether every problem whose yes-instances have efficiently checkable certificates also has an efficient algorithm for finding or deciding them. In symbols, the question is whether

\[ \textsf{P} = \textsf{NP}. \]

This is the most famous open problem in theoretical computer science. The rest of this book will not solve it; no one currently knows how to do so. Instead, we will build the language, theorems, and techniques that explain why the question is so central and so difficult.

Why lower bounds are hard

An upper bound says that a problem can be solved within some resource limit. For example, saying that graph reachability is solvable in linear time on adjacency lists is an upper bound. To prove an upper bound, it is enough to present an algorithm and analyze it.

A lower bound says that every algorithm in a model requires at least some amount of resource. Lower bounds are much harder because they must rule out all possible algorithms, including algorithms no one has imagined.

For example, to prove that SAT is not in P, one would need to prove that no polynomial-time algorithm decides SAT. This means excluding every possible clever representation, every possible hidden structure, every possible future algorithmic insight. Complexity theory has powerful lower-bound results for restricted models, such as certain circuit classes, decision trees, and communication protocols, but proving strong lower bounds for general polynomial-time computation remains beyond current techniques.

This book will repeatedly return to this tension. We can prove many conditional statements and many separations between classes. We can prove hierarchy theorems showing that more time or space can solve strictly more problems under suitable conditions, beginning with the foundational development of time and space complexity by Hartmanis and Stearns [Hartmanis and Stearns 1965]. Yet the most famous separations, such as P versus NP and NP versus coNP, remain open.

Complexity classes as maps of computational worlds

A complexity class is a collection of problems solvable under a specified resource bound or computational mode. Examples include:

• \(\textsf{P}\): problems decidable in deterministic polynomial time.
• \(\textsf{NP}\): problems whose yes-instances have polynomial-time verifiable certificates.
• \(\textsf{PSPACE}\): problems decidable using polynomial space.
• \(\textsf{BPP}\): problems decidable in polynomial time by randomized algorithms with bounded error.
• \(\textsf{BQP}\): problems decidable in polynomial time by quantum algorithms with bounded error.

These definitions will be made precise later. For now, think of a complexity class as a region on a map. The map is not only about which problems are easy or hard. It also records relationships among resources: time versus space, determinism versus nondeterminism, randomness versus determinism, classical versus quantum computation, uniform versus nonuniform computation, and proof verification versus proof interaction.

For example, \(\textsf{P}\subseteq \textsf{NP}\), because if a problem can be solved in polynomial time, then a verifier can ignore the certificate and solve the problem directly. We also know \(\textsf{P}\subseteq \textsf{PSPACE}\), because a polynomial-time computation can use at most polynomially many tape cells. But whether \(\textsf{P}=\textsf{NP}\) is unknown, and whether \(\textsf{P}=\textsf{PSPACE}\) is also unknown.

Complexity theory is full of such relationships. Some are known equalities. Some are known containments. Some are known strict containments. Many are open questions. A major goal of this book is to help you read these relationships not as isolated facts, but as parts of a coherent structure.

How this book is organized

The first part of the book builds the foundations. We begin with what complexity theory studies, then formalize models of computation and explain why many details of the machine model do not matter up to polynomial factors. We define time, space, encodings, languages, reductions, and the basic classes P, NP, EXP, L, PSPACE, and related classes.

The next part develops NP-completeness. We study nondeterminism, verifiers, certificates, the Cook–Levin theorem, and a working library of reductions. This is where the subject becomes practical: after learning these techniques, you will be able to recognize and prove NP-completeness for many problems.

Then we move beyond NP. We study coNP, the polynomial hierarchy, diagonalization, hierarchy theorems, space complexity, Savitch’s theorem, games, alternation, and PSPACE. These chapters show that complexity theory is not only about P versus NP. It is a broad theory of resources and modes of computation.

The middle chapters study circuits and randomness. Boolean circuits give a nonuniform model of computation and lead naturally to circuit lower bounds. Randomized computation introduces classes such as RP, ZPP, BPP, and PP, and raises a subtle question: is randomness truly a computational resource, or can efficient deterministic computation simulate it?

The later chapters widen the lens further. Counting complexity studies problems where the goal is not merely to decide whether a solution exists but to count how many solutions there are. Interactive proofs and probabilistically checkable proofs connect computation with verification, approximation, and proof systems. Communication complexity studies how much information two parties must exchange to compute a function. Descriptive complexity connects computation to logic. Pseudorandomness, average-case complexity, fine-grained complexity, parameterized complexity, and quantum complexity show how modern complexity theory reaches into cryptography, algorithms, logic, physics-inspired computation, and lower-bound methodology.

The final chapter returns to open problems. By then, questions such as P versus NP, NP versus coNP, circuit lower bounds, derandomization, quantum advantage, and proof complexity should feel less like slogans and more like precise mathematical frontiers.

How to think while reading

Complexity theory rewards a particular style of thinking.

First, always ask what the input is and how it is encoded. A statement about graphs, integers, formulas, or machines becomes mathematically meaningful only after the input representation is clear.

Second, distinguish a problem from an algorithm. A problem may have many algorithms. Complexity theory classifies the problem by the best resource bounds achievable by any algorithm in a specified model.

Third, pay close attention to quantifiers. The difference between “there exists a certificate” and “for every certificate” is the difference between NP and coNP-like behavior. The alternation of existential and universal quantifiers leads to the polynomial hierarchy and to alternation.

Fourth, remember that reductions have direction. If \(A\) reduces to \(B\), then an efficient algorithm for \(B\) gives an efficient algorithm for \(A\). The target problem \(B\) is at least as hard as the source problem \(A\), not the other way around.

Fifth, separate known theorems from conjectures. “SAT is NP-complete” is a theorem. “SAT has no polynomial-time algorithm” is not known. “P is probably not equal to NP” is a widely held belief, but it is not a theorem.

Finally, use examples actively. When you learn a definition, test it on \(\textsf{SAT}\), \(\textsf{PATH}\), \(\textsf{CLIQUE}\), or another familiar problem. Complexity theory is abstract, but its abstractions become clear through repeated contact with concrete problems.

A first compass

Here is the central compass for the book:

\[ \text{models} \longrightarrow \text{resources} \longrightarrow \text{classes} \longrightarrow \text{reductions} \longrightarrow \text{lower bounds and barriers}. \]

We begin by defining models of computation. On those models, we measure resources. Resource bounds define complexity classes. Reductions compare the difficulty of problems and identify complete problems. Lower bounds try to prove that certain resources are necessary. Barriers explain why some natural proof techniques cannot resolve the deepest open questions.

This compass will guide every chapter. Some chapters will feel algebraic, with definitions and containments. Some will feel combinatorial, with reductions and graph problems. Some will feel logical, probabilistic, or information-theoretic. But the underlying question remains the same:

What makes a computational problem easy, hard, or impossible to solve within a given resource bound?

That question is the beginning of computational complexity theory.

References

Arora, Sanjeev, and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

Cobham, Alan. “The Intrinsic Computational Difficulty of Functions.” In Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress, edited by Yehoshua Bar-Hillel, 24–30. North-Holland, 1965.

Cook, Stephen A. “The Complexity of Theorem-Proving Procedures.” In Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151–158. ACM, 1971.

Edmonds, Jack. “Paths, Trees, and Flowers.” Canadian Journal of Mathematics 17 (1965): 449–467.

Hartmanis, Juris, and Richard E. Stearns. “On the Computational Complexity of Algorithms.” Transactions of the American Mathematical Society 117 (1965): 285–306.

Karp, Richard M. “Reducibility among Combinatorial Problems.” In Complexity of Computer Computations, edited by Raymond E. Miller and James W. Thatcher, 85–103. Plenum Press, 1972.

Papadimitriou, Christos H. Computational Complexity. Addison-Wesley, 1994.

Turing, Alan M. “On Computable Numbers, with an Application to the Entscheidungsproblem.” Proceedings of the London Mathematical Society, Series 2, 42 (1936): 230–265.