1 Foundations

Complexity classes organize computational problems by the resources needed to solve them. The most common measures are running time, memory usage, randomness, and communication. By grouping problems in this way, complexity theory provides a framework for comparing difficulty and for studying the inherent limits of efficient algorithms.

1.1 Computational problems and decision problems

A computational problem asks for a valid output on each input instance. Many complexity classes focus on decision problems, where the answer is simply yes or no. This restriction is useful because decision problems are easier to formalize and can often represent broader tasks through encoding. For example, searching, counting, and optimization questions are frequently transformed into decision versions before analysis.

1.2 Resource bounds

Resource bounds specify which computations are considered feasible within a given class. A problem belongs to a class if some algorithm or machine model solves it while staying within the allowed resource limit on all inputs of a given size. These bounds are typically expressed asymptotically, using functions of the input length.

1.2.1 Time complexity

Time complexity measures how many steps an algorithm takes. Classes defined by time bounds capture the tradeoff between input size and runtime, such as polynomial time or exponential time. Time is the most familiar resource because it directly reflects how long a computation may take.

1.2.2 Space complexity

Space complexity measures the amount of memory used during computation. Unlike time, space can often be reused, so a machine may take many steps while keeping its memory footprint small. Space-bounded classes are especially important in settings where storage is limited or where reversible use of memory matters.

1.2.3 Randomness and nondeterminism

Randomness allows an algorithm to make coin-flip-like choices, leading to probabilistic classes that measure success with bounded error or one-sided error. Nondeterminism models a computation that may branch into many possible paths, accepting if at least one path succeeds. These ideas broaden the notion of efficient computation beyond purely deterministic procedures.

1.3 Formal machine models

Complexity classes are usually defined using abstract machines or equivalent formal systems. The choice of model matters less than the resource bound, because many standard models simulate one another with at most polynomial overhead. This robustness makes complexity classes meaningful across a wide range of computational settings.

1.3.1 Turing machines

Turing machines are the classic model of computation in complexity theory. They provide a precise way to define time and space bounds and are flexible enough to encode algorithms over strings and symbols. Deterministic, nondeterministic, and probabilistic variants are all widely used.

1.3.2 Boolean circuits

Boolean circuits represent computation as a network of logic gates arranged in layers. They are especially useful for studying parallel computation and very small-depth computation. Circuit families also connect complexity theory with hardware-style models and lower-bound questions.

1.3.3 Randomized and nondeterministic models

Randomized machines incorporate probabilistic choices, while nondeterministic machines branch over multiple possible computations. These models are not intended as physical devices so much as theoretical tools for measuring complexity under different kinds of computational power. They help define classes related to verification, approximation, and counting.

2 Major complexity classes

Major complexity classes form the backbone of the field. They include central categories for efficient deterministic computation, verification, randomness, counting, and space-limited computation. Many of the most important open questions in theoretical computer science concern the relationships among these classes.

2.1 Deterministic classes

Deterministic classes consist of problems solvable by a machine with a unique, predictable computation path. They often serve as baseline classes against which others are compared. Several deterministic classes mark widely studied thresholds of feasibility.

2.1.1 P

P is the class of decision problems solvable in polynomial time by a deterministic algorithm. It is commonly treated as the formal model of efficient computation. Problems in P are considered tractable in principle, though polynomial time may still be impractical for large instances.

2.1.2 EXP

EXP contains problems solvable in exponential time. These problems are generally viewed as intractable for large inputs because the running time grows very rapidly. The class is useful for proving that some problems require substantially more than polynomial time.

2.1.3 L and NL

L is the class of problems solvable using logarithmic space, while NL allows nondeterministic logarithmic space. These classes capture computations with extremely limited memory. They are central in studying reachability, streaming-style computation, and the power of small workspace.

2.2 Nondeterministic classes

Nondeterministic classes are defined by machines that may guess a solution path and verify it efficiently. They are closely tied to certificates and proof checking. Such classes play a major role in the study of search, verification, and computational hardness.

2.2.1 NP

NP consists of decision problems whose yes-instances have polynomial-size certificates that can be verified in polynomial time. It includes many natural problems from combinatorics, logic, and optimization. The question of whether P equals NP is among the best known problems in computer science.

2.2.2 co-NP

co-NP is the class of complements of problems in NP. A problem in co-NP has efficiently verifiable certificates for no-instances rather than yes-instances. The structure of co-NP is important in understanding asymmetry between proving that something exists and proving that it does not.

2.2.3 NEXP

NEXP is the class of problems solvable by a nondeterministic machine in exponential time. It is a far larger class than NP and is often used in very strong lower-bound and completeness results. Many problems in NEXP arise from succinct representations or highly compressed input descriptions.

2.3 Space-bounded classes

Space-bounded classes measure the memory required to solve problems, often independent of how much time is spent. They are especially important because some space bounds lead to strong structural theorems. These classes also include problems that can be solved with surprisingly little storage.

2.3.1 PSPACE

PSPACE contains problems solvable using polynomial space. It includes many decision problems involving quantifiers, games, and iterative reasoning. Because space can be reused, PSPACE may contain problems that would require much longer time in straightforward brute-force approaches.

2.3.2 EXPSPACE

EXPSPACE is the class of problems solvable using exponential space. It lies well above PSPACE and includes very demanding problems in terms of memory usage. This class is relevant when describing computations that require enormous intermediate storage.

2.3.3 Logarithmic-space classes

Logarithmic-space classes study computation with memory logarithmic in the input size. Besides L and NL, there are related classes that refine the notion of small-space computation. These classes are often connected to graph algorithms, transitive closure, and memory-efficient processing.

2.4 Randomized classes

Randomized classes allow algorithms to use random bits during computation. They are designed to capture efficient procedures that may occasionally err but do so with controlled probability. Randomization often simplifies algorithms and can improve expected performance.

2.4.1 BPP

BPP consists of problems solvable in polynomial time with bounded error using randomization. The error probability is small on every input and can typically be reduced further by repetition. BPP is widely considered a natural model for efficient randomized computation.

2.4.2 RP

RP is the class of problems solvable in polynomial time with one-sided error. For inputs in the language, the algorithm accepts with positive probability, while for nonmembers it never accepts. This asymmetry is useful in randomized verification and algorithm design.

2.4.3 ZPP

ZPP consists of problems solvable in expected polynomial time with zero error. Algorithms in this class always produce the correct answer, though the time taken may vary. ZPP can be viewed as a highly reliable form of randomized computation.

2.5 Counting classes

Counting classes extend decision complexity by asking how many accepting witnesses or solutions a problem has. These classes are central in enumerative combinatorics, probabilistic reasoning, and hardness theory. They often encode problems that are harder than their decision counterparts.

2.5.1 #P

#P counts the number of accepting paths of an NP machine, or equivalently the number of certificates for a problem. It is a counting analogue of NP rather than a decision class. Many important combinatorial counting tasks are complete for #P.

2.5.2 PP

PP contains problems solvable by a probabilistic machine that accepts when more than half of its computation paths accept. It is a powerful class related to majority vote over nondeterministic choices. PP is often used to compare decision and counting complexity.

2.5.3 Modulo-based classes

Modulo-based classes classify problems according to the number of accepting paths modulo a fixed number. These classes help capture arithmetic properties of solution counts and can differ sharply from ordinary acceptance classes. They are useful in fine-grained studies of counting and algebraic computation.

3 Relationships between classes

Complexity classes are connected by containment, separation, and reduction results. These relationships explain how different resource bounds compare and how difficult problems can be transferred from one setting to another. The structure of these inclusions forms a large part of complexity theory.

3.1 Inclusion relations

Containment relations show when one class lies inside another. Some are immediate from the definitions, while others require nontrivial theorems. Inclusion diagrams are a standard way to summarize what is known about computational power.

3.1.1 Standard containments

Many basic containments are known, such as L contained in NL, NL contained in P, and P contained in NP and PSPACE. Randomized and counting classes also fit into larger frameworks through known inclusions. These standard relations provide a map of the complexity landscape.

3.1.2 Known separations

Some separations are proved unconditionally, especially when resource bounds differ greatly. For example, hierarchy theorems show that more time or space can yield strictly more power under suitable conditions. However, many famous separations, such as P versus NP, remain unresolved.

3.1.3 Open problems

A number of fundamental containment questions remain open. The most famous are whether P equals NP, whether NP equals co-NP, and where randomized classes sit relative to deterministic ones. These problems guide much of modern complexity research.

3.2 Completeness

Completeness identifies the hardest problems in a class under a chosen type of reduction. A complete problem is one that is in the class and can represent every other problem in the same class through efficient transformation. Completeness results are among the most important tools for classifying difficulty.

3.2.1 Reductions

Reductions are efficient mappings from one problem to another. If problem A reduces to problem B, then solving B efficiently gives a solution for A. Different reduction types reflect different notions of resource preservation and hardness.

3.2.2 Complete problems

Complete problems serve as canonical representatives of a class. For NP, satisfiability is the best-known complete problem, while reachability and quantified formulas are complete for other classes. Studying complete problems helps identify structural features shared by all problems in a class.

3.2.3 Hardness notions

Hardness measures how difficult a problem is relative to a class, even if the problem itself is not a member of that class. A problem may be NP-hard, PSPACE-hard, or hard for many other classes under suitable reductions. Hardness is central in proving that efficient algorithms are unlikely to exist.

3.3 Hierarchy theorems

Hierarchy theorems show that increasing resources can strictly enlarge computational power. They are among the most general results in complexity theory. Such theorems demonstrate that no single small bound captures all efficient computation.

3.3.1 Time hierarchy theorem

The time hierarchy theorem states, roughly, that more time allows the solution of some problems not solvable with less time. It formalizes the intuition that larger time budgets should permit strictly more computation. This result underlies many separations between time-based classes.

3.3.2 Space hierarchy theorem

The space hierarchy theorem shows that larger space bounds also yield strictly more power, under suitable conditions. It is often easier to work with than time hierarchy because space usage has strong structural properties. The theorem supports the idea that memory limits sharply constrain computation.

3.3.3 Polynomial hierarchy

The polynomial hierarchy is a layered family of classes built from alternating quantifiers and NP-like behavior. It generalizes NP and co-NP through multiple levels of existential and universal reasoning. The hierarchy is deeply connected to logic, game semantics, and collapse phenomena.

4 Advanced class families

Advanced class families refine complexity theory beyond the standard time-and-space classes. They study restricted circuits, parallel computation, interactive proof systems, and logical descriptions of problems. These areas reveal how different computational resources interact.

4.1 Circuit complexity classes

Circuit classes classify problems by the depth, size, and types of gates in Boolean circuits. They are well suited to examining parallelism and very fast computation. Circuit lower bounds are also a major route to proving computational limitations.

4.1.1 AC0

AC0 contains problems solvable by constant-depth, polynomial-size circuits with unbounded fan-in AND and OR gates. It captures extremely shallow computation. Many arithmetic and parity-related tasks are not in AC0.

4.1.2 NC

NC is the class of problems solvable by polylogarithmic-depth, polynomial-size circuits. It is often interpreted as the class of efficiently parallelizable problems. NC provides a formal basis for comparing sequential and parallel algorithmic efficiency.

4.1.3 TC

TC uses threshold gates, which output based on whether a weighted sum exceeds a threshold. These circuits can express majority-like behavior more naturally than plain Boolean circuits. They are important in understanding the role of counting and arithmetic in computation.

4.2 Parallel computation classes

Parallel computation classes focus on tasks that can be divided among many processors. They formalize which problems can be solved quickly when many operations happen simultaneously. This area connects theoretical complexity with practical parallel algorithms.

4.2.1 NC hierarchy

The NC hierarchy refines parallel complexity by depth and degree of parallelism. Different levels describe finer distinctions in how quickly a problem can be solved using parallel resources. The hierarchy helps distinguish highly parallelizable tasks from those requiring more sequential dependence.

PRAM-related classes arise from the parallel random-access machine model. They study how shared-memory parallel processors behave under different synchronization and access assumptions. These classes are useful in analyzing idealized parallel algorithms and their overheads.

4.3 Interactive and proof-based classes

Interactive and proof-based classes study computation in which a verifier interacts with a prover or uses proof systems. They capture notions of efficient checking rather than direct computation alone. These ideas have reshaped the understanding of what can be verified in polynomial time.

4.3.1 IP

IP is the class of problems having interactive proof systems with a polynomial-time verifier. It allows a verifier to exchange messages with a powerful prover and still decide correctly. The class is notable for linking randomness, interaction, and proof verification.

4.3.2 PCP

PCP describes problems with probabilistically checkable proofs, where a verifier reads only a small portion of a proof. This framework shows that some proofs can be checked with very limited inspection. PCP theory is a foundational tool in hardness of approximation.

4.3.3 AM

AM is a class of interactive proof systems with a restricted two-message structure. It is often viewed as a randomized analogue of NP with interaction. AM captures problems whose solutions can be efficiently checked after a brief exchange.

4.4 Descriptive complexity

Descriptive complexity characterizes complexity classes using logic rather than machines. It links computational difficulty to the expressive power of logical languages. This perspective often reveals deep structural correspondences.

4.4.1 FO and MSO characterizations

First-order logic and monadic second-order logic can describe certain classes of finite structures. When restricted appropriately, these logics correspond to low-level circuit or parallel classes. Such characterizations provide symbolic descriptions of computation.

4.4.2 Logic-based complexity correspondences

Logic-based correspondences identify complexity classes with families of logical formulas under specific semantic conditions. These relationships connect proof theory, finite model theory, and algorithms. They are especially valuable for understanding why some problems are easy or hard to express.

5 Applications and significance

Complexity classes are not only abstract categories; they also shape practical and conceptual work across computer science. They influence algorithm design, cryptographic assumptions, approximation methods, and the study of computational limits. Their significance lies in both classification and explanation.

5.1 Algorithm design

Complexity theory guides the search for efficient algorithms by indicating which problems may be solvable in polynomial time and which are likely to require heavier resources. When a problem is known to lie in a low complexity class, algorithm designers can aim for practical methods with provable guarantees. Conversely, hardness results may shift attention toward heuristics or special-case algorithms.

5.2 Cryptography

Cryptography relies on problems that appear computationally difficult. Complexity classes help formalize the security assumptions behind encryption, authentication, and related protocols. The contrast between easy verification and hard inversion is especially important in this area.

5.3 Optimization and approximation

Many optimization problems are too hard to solve exactly, so researchers seek approximate solutions. Complexity classes help determine whether efficient approximation is possible and how close an approximation can be. This perspective has led to deep connections between decision complexity and optimization thresholds.

5.4 Complexity-theoretic reductions

Reductions allow one problem to be translated into another, preserving solvability or hardness. They are a primary method for transferring insights across different domains. Through reductions, a single complete problem can illuminate an entire class of related tasks.

5.5 Limits of efficient computation

Complexity classes clarify what efficient computation can and cannot achieve. They reveal that some problems resist compact algorithms, fast parallelization, or short proofs unless major class collapses occur. In this way, complexity theory provides a rigorous language for the boundaries of algorithmic power.