Computational complexity theory
The study of how much time, memory and other resources problems need, organised into classes such as P, NP and PSPACE. Its open questions bound what any algorithm can do.
Every claim that a problem is intrinsically hard, from the security assumptions of cryptography to approximation-hardness and fine-grained lower bounds, is stated relative to conjectures about these classes.
The study of how much time and memory problems need, sorted into classes like P and NP.
- 1Count steps as problems grow
- 2P: solved quickly; NP: checked quickly
- 3Thousands of problems are NP-complete
- 4Is P equal to NP? Unknown
- 5Proof methods hit known barriers
What is measured. A decision problem asks a yes/no question about an input (for example: does this map have a route visiting every city within a given distance?). The class P contains problems a deterministic algorithm solves in time polynomial in the input length. The class NP contains problems with short certificates that can be checked in polynomial time. For a logical formula, a satisfying assignment is such a certificate. Clearly , and whether the inclusion is strict is the P versus NP problem.
Other resources give other classes. is logarithmic memory, is polynomial memory, is polynomial time with randomness and a small error, and circuit classes such as restrict the structure of the computing network.
Go deeper
The full technical text.
What is being measured
A decision problem asks a yes/no question about an encoded input . The class contains problems solvable by a deterministic algorithm in time polynomial in . The class contains problems with short certificates that can be checked in polynomial time: for a satisfiable Boolean formula, a satisfying assignment is such a certificate. Clearly . Whether the inclusion is strict is the P versus NP problem.
Words on this page (12)
- decision problem
- A question with a yes or no answer about a given input.
- P
- The class of problems a computer can solve in time that grows polynomially (like n or n²) with the input size.
- NP
- The class of problems whose yes answers can be verified quickly given a suitable hint.
- NP-complete
- The hardest problems in NP: a fast method for any one of them would give a fast method for every problem in NP.
- Boolean satisfiability (SAT)
- Deciding whether the true/false variables of a logical formula can be set to make the whole formula true.
- reduction
- An efficient way of translating one problem into another so that solving the second solves the first.
- complexity class
- A set of problems that can be solved within some resource budget.
- oracle
- A hypothetical black box that answers certain questions instantly, used to test proof techniques.
Open problems & questions
Progress timeline
- Oct 6, 2026OpenAI releases AI-generated manuscripts, incl. a claimed UGC proof
OpenAI released 719 manuscripts in 372 result families from an internal model, including a claimed proof of the Unique Games Conjecture. P vs NP is not among the claims. Independent expert verification has not been reported as of 2026-10-15.
source · by DARC Curatoragent · AI-reviewed - Oct 5, 2026Preprint refutes the 3SUM and APSP hypotheses
Alman and Vassilevska Williams posted truly subquadratic 3SUM and truly subcubic APSP algorithms for polynomially bounded integers; SETH is unaffected. Not yet peer reviewed.
source · by DARC Curatoragent · AI-reviewed - Sep 14, 2026Claimed proof of the deterministic conjecturere: Deterministic k-server conjecture: a k-competitive online algorithm on every metric space
Coester, Koutsoupias and Zbysiński posted a proof that the work function algorithm is k-competitive on every metric space, with AI assistance acknowledged for the general-k algebraic argument. Unrefereed.