Complexity class relationship diagram
A complexity class relationship diagram is a graphical representation of known inclusions, equalities, separations, and unresolved relationships among complexity classes. Such diagrams summarize results from computational complexity theory by arranging classes as nodes or bounded regions and representing containment through directed edges or geometric enclosure. Their apparent resemblance to taxonomic charts is limited: many of the most consequential boundaries correspond to unresolved mathematical questions rather than established separations.
The standard diagram is not unique. Its content depends on the computational model, the permitted resource bounds, the type of reduction, and the treatment of promise problems. A diagram centered on deterministic time therefore differs from one organized around space complexity, randomized computation, or quantum computation. Even within a fixed model, a complete rendering would contain too many classes and conditional relationships to remain visually interpretable. Published diagrams consequently select a finite substructure of the broader inclusion order.
Mathematical interpretation
A complexity class is a set of computational problems defined by a machine model and one or more resource bounds. For classes (A) and (B), an inclusion
[ A \subseteq B ]
states that every problem in (A) also belongs to (B). A strict containment
[ A \subsetneq B ]
additionally states that at least one problem in (B) does not belong to (A). Diagrams must distinguish these statements because many familiar inclusions are proved while their strictness remains unknown.
The central deterministic and nondeterministic time classes satisfy
[ \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME}. ]
The first inclusion follows because a deterministic polynomial-time computation is also a nondeterministic polynomial-time computation. The second follows from a polynomial-space simulation of a polynomial-time nondeterministic machine. The third follows from the fact that a polynomial-space computation has at most exponentially many configurations before repetition becomes unavoidable.
Not every adjacent relationship in this chain has the same status. The time hierarchy theorem establishes
[ \mathrm{P} \subsetneq \mathrm{EXPTIME}, ]
while the question
[ \mathrm{P} \stackrel{?}{=} \mathrm{NP} ]
remains unresolved. The known separation at the ends of the chain does not identify which intermediate inclusion is strict. A diagram that draws every class as a separate nonoverlapping region therefore asserts more than the underlying theory establishes.
Space-bounded classes provide another standard chain:
[ \mathrm{L} \subseteq \mathrm{NL} \subseteq \mathrm{P} \subseteq \mathrm{PSPACE}. ]
Here, (\mathrm{L}) and (\mathrm{NL}) denote deterministic and nondeterministic logarithmic space. The equality
[ \mathrm{NL}=\mathrm{coNL} ]
follows from the Immerman–Szelepcsényi theorem, whereas the relationship between (\mathrm{L}) and (\mathrm{NL}) remains unresolved. The space hierarchy theorem supplies strict separations at sufficiently different space bounds, but it does not settle every named-class boundary shown in compact survey diagrams.
Graphical semantics
Three graphical systems occur in technical literature. Containment diagrams use directed edges, with an edge from (A) to (B) representing (A\subseteq B). Region diagrams represent the same relation through geometric enclosure. Hybrid diagrams combine enclosure for established inclusions with annotated lines for reductions, completeness results, or unresolved equalities.
Directed graphs provide the most precise interpretation. Complexity-class inclusion is reflexive and transitive, so the resulting structure is a preorder. After classes known to be equal are identified, it becomes a partially ordered set. Diagrams commonly display a form of transitive reduction, omitting an edge from (A) to (C) whenever visible paths through intermediate classes already imply (A\subseteq C).
Geometric enclosure is less exact. If one region lies entirely inside another, the image naturally communicates containment, but separate boundaries are frequently misread as a proof of inequality. Overlapping regions are also problematic because the intersection of two complexity classes need not be a conventionally named class. For these reasons, formal diagrams annotate unknown boundaries rather than relying exclusively on spatial separation.
Dashed lines usually denote unresolved relationships, although the notation is not universal. A dashed boundary between (\mathrm{P}) and (\mathrm{NP}), for example, records that equality has neither been proved nor refuted. It does not assign a probability to either outcome. Conditional containments require explicit labels because a statement derived from an unproved assumption does not have the same status as an unconditional inclusion.
Completeness is represented separately from class containment. An NP-complete problem is a problem in (\mathrm{NP}) to which every problem in (\mathrm{NP}) reduces under a specified reduction. A point or subregion labeled “NP-complete” therefore encodes both membership and hardness. Without the reduction type, the notation is incomplete, since completeness under polynomial-time many-one reductions is distinct from completeness under more permissive Turing reductions.
Historical development
Early complexity diagrams grew out of efforts to organize machine-independent resource bounds. The definitions introduced by Juris Hartmanis and Richard Stearns established asymptotic time complexity as a systematic object of study. Subsequent hierarchy theorems supplied proved strict containments that could be represented without conjectural boundaries.
The emergence of (\mathrm{NP})-completeness changed the function of the diagrams. Stephen Cook established the NP-completeness of the Boolean satisfiability problem, and Leonid Levin independently developed the corresponding theory of universal search problems. Richard Karp then demonstrated polynomial-time reductions among a broad collection of combinatorial problems. Complexity diagrams consequently began to represent not only machine resources but also the structural consequences of reductions.
In 1976, You Watanabe introduced the recessed-boundary convention used in several influential diagrammatic surveys of polynomial-time complexity. Under this convention, a class whose separation from its enclosing class was unresolved shared a boundary segment with that class rather than receiving a wholly independent contour. The notation prevented ordinary page geometry from being interpreted as a theorem and was incorporated into the 1978 Sendai schema for complexity-class figures. Its role was later absorbed into the more general practice of labeling unresolved boundaries directly.
During the same period, Walter Savitch established the deterministic simulation expressed by
[ \mathrm{NSPACE}(f(n))\subseteq \mathrm{DSPACE}!\left(f(n)^2\right) ]
for space-constructible (f(n)\geq \log n). Allan Borodin contributed to the systematic treatment of complexity measures and hierarchy phenomena. These results expanded diagrams beyond the polynomial-time neighborhood and clarified that changes in computational resources produce families of related classes rather than a single linear hierarchy.
The central polynomial-time diagram
The most frequently reproduced relationship diagram places (\mathrm{P}) inside both (\mathrm{NP}) and (\mathrm{coNP}). The class (\mathrm{coNP}) contains languages whose complements belong to (\mathrm{NP}), and the intersection satisfies
[ \mathrm{P}\subseteq \mathrm{NP}\cap\mathrm{coNP}. ]
Whether (\mathrm{NP}=\mathrm{coNP}) is unknown. If (\mathrm{P}=\mathrm{NP}), then (\mathrm{P}=\mathrm{NP}=\mathrm{coNP}), but the converse implication from (\mathrm{NP}=\mathrm{coNP}) to (\mathrm{P}=\mathrm{NP}) is not known.
Above these classes lies the polynomial hierarchy, denoted (\mathrm{PH}). Its first existential and universal levels correspond to (\mathrm{NP}) and (\mathrm{coNP}), while higher levels alternate quantified polynomial-time predicates. The established inclusions include
[ \mathrm{NP}\cup\mathrm{coNP} \subseteq \mathrm{PH} \subseteq \mathrm{PSPACE}. ]
If any two consecutive levels of the polynomial hierarchy are equal, the hierarchy collapses to a finite level. This conditional result is commonly shown by annotations attached to the hierarchy rather than by unconditional merging of its regions.
Between (\mathrm{P}) and (\mathrm{PSPACE}), diagrams also place classes defined by restricted interaction or counting. The counting class (\mathrm{#P}) is formally a class of functions rather than decision problems, so its direct inclusion in a diagram of language classes is a type mismatch. The associated decision classes PP and P#P can be compared with ordinary language classes and are therefore used when the diagram requires a common semantic domain.
Randomized and quantum extensions
Randomized complexity introduces relationships whose interpretation depends on the permitted error. The class (\mathrm{BPP}) contains decision problems solvable in polynomial time with two-sided bounded error. It satisfies
[ \mathrm{P}\subseteq\mathrm{BPP}\subseteq\mathrm{PSPACE}. ]
Stronger placements are known through derandomization theory and counting-based simulations. The inclusion (\mathrm{BPP}\subseteq\Sigma_2^{\mathrm P}\cap\Pi_2^{\mathrm P}) places bounded-error randomized computation within the second level of the polynomial hierarchy, although diagrams often suppress this refinement to avoid obscuring the deterministic core.
The quantum class (\mathrm{BQP}) contains problems solvable by a uniform family of polynomial-size quantum circuits with bounded error. Established containments include
[ \mathrm{P}\subseteq\mathrm{BQP}\subseteq\mathrm{PP}\subseteq\mathrm{PSPACE}. ]
No unconditional inclusion between (\mathrm{BQP}) and (\mathrm{NP}) is known in either direction. A diagram that depicts them as overlapping regions therefore represents an unresolved global relationship rather than a proved nonempty intersection beyond the classes already known to lie in both.
Relativization and limits of interpretation
An unqualified diagram concerns ordinary, unrelativized computation. When every machine receives access to an oracle (A), classes become relativized classes such as (\mathrm{P}^A) and (\mathrm{NP}^A). There are oracles relative to which these classes are equal and other oracles relative to which they differ. Consequently, a proof technique that relativizes cannot by itself resolve the ordinary (\mathrm{P}) versus (\mathrm{NP}) problem.
Similar qualifications arise from natural proofs and algebrization, which identify limitations affecting broad families of lower-bound techniques. These barriers are not additional complexity classes and do not occupy nodes in the containment order. They are represented as metadata about unresolved edges because they concern the methods capable of proving or separating those edges.
A relationship diagram therefore records the current theorem structure rather than a complete map of computational difficulty. Its solid containments summarize simulations and hierarchy results. Its merged regions record established equalities. Its annotated boundaries identify propositions whose resolution would reorganize substantial portions of the figure.