P (complexity)

Lore & Background

P is defined as the set of languages L for which there exists a deterministic Turing machine M that runs in polynomial time on all inputs, outputs 1 for all x in L, and outputs 0 for all x not in L. P can also be viewed as a uniform family of Boolean circuits, where a language L is in P if and only if there exists a polynomial-time uniform family of Boolean circuits that correctly decides membership in L. The circuit definition can be weakened to use only a logspace uniform family without changing the complexity class. The related class of function problems is FP. Several natural problems are complete for P, including st-connectivity (or reachability) on alternating graphs. P is trivially a subset of NP and co-NP, though most experts believe it is a proper subset—a belief known as the P ≠ NP hypothesis, which remains unproven. P is also at least as large as L (logarithmic space), and it is known that P = AL (alternating logarithmic space). P is no larger than PSPACE, and whether P = PSPACE is an open problem. Several strict containments are known: for example, L ⊊ PSPACE, NL ⊊ PSPACE, DTIME(n) ⊊ DTIME(n²), and P ⊊ EXPTIME.

Reader's Guide

P is a cornerstone of computational complexity theory, representing the class of problems considered efficiently solvable by a deterministic computer. Its significance stems from Cobham's thesis, which equates polynomial time with tractability, though this is a practical rule of thumb rather than a precise boundary. The relationship between P and NP is the most famous open problem in computer science; resolving whether P equals NP would have profound implications for cryptography, optimization, and artificial intelligence. P is also central to understanding the hierarchy of complexity classes, as it sits between L and NP, with known strict containment only relative to EXPTIME. The class P/poly extends P by allowing an advice string, and contains nearly all practical problems, including all of BPP, but also some undecidable problems. Polynomial-time algorithms are closed under composition, making P machine-independent, and languages in P are closed under operations such as reversal, intersection, union, and complementation. Some problems are known to be in P via nonconstructive proofs, such as the Robertson–Seymour theorem guaranteeing a polynomial-time algorithm for toroidal graph embedding without providing a concrete algorithm.

Did You Know?

• P is also known as PTIME or DTIME(n^O(1)).
• Cobham's thesis holds that P is the class of 'efficiently solvable' problems, though this is inexact.
• Many strict containments are known, including L ⊊ PSPACE, NL ⊊ PSPACE, DTIME(n) ⊊ DTIME(n²), and P ⊊ EXPTIME.

Formalizing Hardness and Measuring Resources

Computational complexity theory exists to answer a deceptively simple question: how hard is a problem, really? The field formalizes the intuition that a task is inherently difficult when no algorithm—no matter how clever—can solve it without consuming substantial resources. To make this rigorous, the theory introduces mathematical models of computation and quantifies the resources involved, most commonly time and storage, but also extending to communication volume in communication complexity, gate counts in circuit complexity, and processor counts in parallel computing. One of the field's central roles is to delineate the practical boundaries of what machines can and cannot accomplish. The P versus NP question, one of the seven Millennium Prize Problems, sits squarely within this landscape. Crucially, complexity theory differs from analysis of algorithms, which examines a single specific algorithm's resource needs, by asking a broader question about every conceivable algorithm for a given problem. It also differs from computability theory, which asks whether a problem can be solved algorithmically at all, by imposing explicit restrictions on available resources.

Problems Versus Instances: The Abstraction Principle

A foundational distinction in computational complexity theory separates the problem from any single instance of it. A computational problem is best understood as an infinite collection of instances, each paired with a set of possible solutions. The input string fed to an algorithm is called a problem instance, and it must not be confused with the problem itself. The problem is the abstract question; the instance is a concrete, particular utterance that serves as input. Take primality testing: the problem is the general question of whether a number is prime, while an instance is a specific number such as 15, yielding the answer no. The distinction becomes even sharper with the travelling salesman problem. Because the solution to one instance carries almost no transferable information to another, complexity theory deliberately studies problems as abstract classes rather than individual cases.

Decision Problems as Formal Languages

Decision problems occupy a central position in computational complexity theory. These are computational problems whose answers are strictly binary—yes or no, equivalently 1 or 0. The field's elegant reformulation treats each decision problem as a formal language: the members of the language are precisely those instances for which the correct answer is yes, while non-members correspond to instances answered no. The algorithmic task then becomes deciding whether a given input string belongs to the language under consideration. If the algorithm returns yes, it is said to accept the string; if it returns no, it rejects it. A concrete illustration is the graph-connectivity problem. The input is an arbitrary graph, and the question is whether that graph is connected. The associated formal language is the set of all connected graphs, though pinning down this set precisely requires choosing how graphs are encoded as binary strings. This language-theoretic viewpoint gives the field a clean algebraic structure and unifies diverse computational questions under a single mathematical framework.

Function Problems and Their Reduction to Decisions

A function problem is a computational task in which a single, well-defined output is expected for every input, but that output can be far richer than a simple yes-or-no answer. Prominent examples include the travelling salesman problem and integer factorization, where the desired result is a specific route or a set of prime divisors rather than a binary verdict. At first glance, function problems appear to form a substantially richer category than decision problems. In practice, however, this apparent gap largely dissolves, because many function problems can be recast as decision problems. Consider integer multiplication. Instead of asking an algorithm to compute the product of two integers a and b, one can define a set of triples (a, b, c) satisfying the relation a times b equals c. The question then becomes: given a particular triple, is it a member of this set? Deciding membership in that set is equivalent to verifying the multiplication, and the broader function problem can be recovered by querying the decision version across candidate outputs. This reduction keeps the theoretical framework unified.