Narrative Goldmine

Computational Complexity Theory

33 min read

Properties

Type
  • Class
Resource
  • urn:ngm:class:computational-complexity-theory
Domain
  • artificial-intelligence
Status
  • stable
Maturity
  • established
Quality
  • 0.9
Is a
Has part
Requires
Enables
Generated
  • by: process:vault-migrate/1.0 · at: 2026-09-22T12:41:39.024503178Z
Bridges to
Contrasts with
Depends on
Implemented in layer
Implements
Links
Page resource
  • urn:visionflow:page:04d825c3edc368bf9aa45d8ec7583293647695143e950379402e9269f079b285
Related to
Standardized by
Supports
Uses

The mathematical study of the resources — principally time and memory (space) — required to solve computational problems, and the classification of problems according to their inherent difficulty into complexity classes such as P, NP, PSPACE, BPP, and EXPTIME. It establishes which problems are tractable (solvable efficiently in polynomial time) and which are intractable, and investigates the relationships between complexity classes, most famously the unresolved P vs NP question.

Semantic Classification

Content

Compositional Relationships (Components)

SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:hasPart ai:CircuitComplexity))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:hasPart ai:ProofComplexity))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:hasPart ai:ParameterisedComplexity))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:hasPart ai:FineGrainedComplexity))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:hasPart ai:CountingComplexity))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:hasPart ai:InteractiveProofs))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:hasPart ai:Derandomisation))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:hasPart ai:ApproximationAlgorithms))

Dependency Relationships

SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:requires ai:Algorithm))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:requires ai:TuringMachine))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:requires ai:FormalLanguage))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:requires ai:SetTheory))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:dependsOn ai:ComputabilityTheory))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:dependsOn ai:MathematicalLogic))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:dependsOn ai:InformationTheory))

Capability Relationships

SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:enables ai:QuantumComputing))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:enables ai:CryptographicHardnessAssumption))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:enables ai:SATSolving))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:enables ai:ApproximationAlgorithms))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:enables ai:ComputationalLearningTheory))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:supports ai:AutomatedReasoning))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:supports ai:KnowledgeRepresentation))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:supports ai:OntologyReasoning))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:supports ai:Cryptography))

Implementation Relationships

SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:implements ai:BooleanSatisfiability))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:implements ai:ConstraintSatisfaction))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:implements ai:GraphAlgorithm))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:implements ai:GraphIsomorphism))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:bridgesTo ai:Cryptography))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:bridgesTo ai:MachineLearning))

Uses Relationships

SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:uses ai:Reduction))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:uses ai:Oracle))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:uses ai:ProofSystem))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:uses ai:ProbabilityTheory))

Reduction Relationships

SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:reducesTo ai:TheoreticalComputerScience))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:reducesTo ai:MathematicalLogic))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:reducesTo ai:AlgorithmDesign))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:contrastsWith ai:HeuristicSearch))
SubClassOf(ai:ComputationalComplexityTheory
  ObjectSomeValuesFrom(ai:contrastsWith ai:ComputabilityTheory))

About

  • Computational complexity theory provides the mathematical scaffolding for understanding which computational problems are tractable and which are fundamentally hard, regardless of the cleverness of individual algorithms or the speed of future hardware. Its core objects are complexity classes — sets of problems characterised by shared resource bounds — and the reductions that transfer hardness between problems. The polynomial-time many-one reduction (Karp reduction) is the canonical tool: if problem A reduces to problem B, any efficient algorithm for B yields an efficient algorithm for A, so B is “at least as hard” as A. This allows complexity theory to identify complete problems — problems that are both in a class and as hard as any problem in it — as the hardest representatives of each class. The NP-complete problems (3-SAT, Hamiltonian cycle, Graph Algorithm colouring, travelling salesman decision version) and the PSPACE-complete problems (quantified Boolean formula, TQBF) are the most practically significant instances. The unresolved P vs NP question — whether every problem verifiable in polynomial time is also solvable in polynomial time — is widely regarded as the most important open problem in mathematics, because a proof that P = NP (or P ≠ NP) would have profound implications for Cryptography, Artificial Intelligence, Optimisation, and Machine Learning.
  • The classification framework developed by complexity theory has three foundational pillars. First, the computational model: most complexity classes are defined relative to the Turing Machine (deterministic, non-deterministic, probabilistic, quantum), though the Circuit Complexity model captures fine-grained Boolean circuit depth and size, and communication complexity captures multi-party information exchange costs. Each model captures a different facet of computational resource expenditure, and their relationships illuminate fundamental questions about what computation fundamentally is and what resources it irreducibly consumes. Second, the resource bound: time, space, randomness, alternation, interaction, communication, and quantum entanglement all define distinct resource dimensions, each yielding a hierarchy of complexity classes under tighter and tighter bounds. Third, completeness: identifying problems that are hardest within a class — NP-complete, PSPACE-complete, P-complete — focuses attention on canonical representatives of hard problem families and enables systematic transfer of hardness results through reduction chains. When a new problem is proved NP-complete, it inherits the entire weight of complexity-theoretic evidence that no polynomial-time algorithm exists for it; when a problem is shown to be in P, it inherits the efficiency guarantees of the polynomial-time computation model.
  • The distinction between worst-case and average-case complexity is one of the field’s deepest subtleties. Classical NP-hardness is a worst-case notion: an NP-hard problem may have no polynomial-time algorithm for the hardest inputs, but such inputs might be rare in practice. Average-Case Complexity (Levin, 1986) formalises hardness for randomly generated inputs from a natural distribution; the class DistNP captures problems that are hard on average under a distribution, and average-case completeness results provide stronger evidence of practical intractability. This distinction is particularly important for Machine Learning and Cryptography: practical Cryptographic Hardness Assumptions are average-case assumptions (integer factoring must be hard for random large integers, not just worst-case ones). The connection between worst-case and average-case complexity — when average-case hardness follows from worst-case hardness — is a central open problem in the field, with partial progress through worst-case to average-case reductions for lattice problems (forming the basis of post-quantum cryptography) and for problems in algebraic settings (error-correcting codes, random matrix theory).
  • The theory also addresses resource bounds beyond time and space. Randomised Algorithms introduce the class BPP (bounded-error probabilistic polynomial time) and RP; the question of whether P = BPP (i.e., whether randomness helps polynomial-time computation) is related to Derandomisation results connecting algorithmic pseudorandomness with Circuit Complexity lower bounds. Interactive Proofs (IP) model computation where a powerful prover convinces a polynomial-time probabilistic verifier; the fundamental result IP = PSPACE (Shamir 1992) shows that every problem solvable in polynomial space admits an interactive proof. The probabilistically checkable proofs (PCP) theorem, proved in the early 1990s, establishes that every NP proof can be checked by reading only a constant number of random bits, implying tight inapproximability results: many NP-hard Optimisation problems cannot be approximated to within a constant factor in polynomial time unless P = NP.
  • The interface between computational complexity and Machine Learning has become one of the most active research frontiers. Computational Learning Theory, introduced by Valiant (1984) in the PAC (probably approximately correct) framework, uses complexity theory to characterise which concept classes are learnable from polynomial-size samples in polynomial time. Recent results show that training a one-hidden-layer Neural Network to near-optimality is NP-hard in the worst case (Blum and Rivest, 1992, and subsequent work), motivating the study of efficiently learnable subclasses. Conversely, Machine Learning methods — particularly SAT Solving using neural portfolio solvers — are being applied to complexity problems, creating a productive bidirectional interface. The Fine-Grained Complexity programme, inaugurated by Impagliazzo, Paturi, and Zane around 2001, uses the Strong Exponential Time Hypothesis (SETH) — that k-SAT requires near-exponential time — to derive tight conditional lower bounds for problems within P: edit distance, longest common subsequence, sequence alignment, and many Data Structure and Graph Algorithm problems cannot be significantly accelerated unless SETH fails. This programme connects theoretical complexity to the practical efficiency of fundamental algorithms and creates a rich taxonomy of problems within the polynomial-time class that mirrors the NP-completeness taxonomy at a finer grain.
  • The theory also addresses resource bounds beyond time and space. Randomised Algorithms introduce the class BPP (bounded-error probabilistic polynomial time) and RP; the question of whether P = BPP (i.e., whether randomness helps polynomial-time computation) is related to Derandomisation results connecting algorithmic pseudorandomness with Circuit Complexity lower bounds. Interactive Proofs (IP) model computation where a powerful prover convinces a polynomial-time probabilistic verifier; the fundamental result IP = PSPACE (Shamir 1992) shows that every problem solvable in polynomial space admits an interactive proof. The probabilistically checkable proofs (PCP) theorem, proved in the early 1990s, establishes that every NP proof can be checked by reading only a constant number of random bits, implying tight inapproximability results: many NP-hard Optimisation problems cannot be approximated to within a constant factor in polynomial time unless P = NP.
  • The interface between computational complexity and Machine Learning has become one of the most active research frontiers. Computational Learning Theory, introduced by Valiant (1984) in the PAC (probably approximately correct) framework, uses complexity theory to characterise which concept classes are learnable from polynomial-size samples in polynomial time. Recent results show that training a one-hidden-layer Neural Network to near-optimality is NP-hard in the worst case (Blum and Rivest, 1992, and subsequent work), motivating the study of efficiently learnable subclasses. Conversely, Machine Learning methods — particularly SAT Solving using neural portfolio solvers — are being applied to complexity problems, creating a productive bidirectional interface.

Components / Architecture

  • Complexity Class Hierarchy
    • P (deterministic polynomial time): problems solvable by a deterministic Turing Machine in O(n^k) time for some constant k, including sorting, shortest paths, linear programming, and primality testing (AKS, 2002).
    • NP (non-deterministic polynomial time): the class of decision problems with polynomial-time verifiable certificates; equivalent to problems solvable by a non-deterministic Turing Machine in polynomial time. Contains all NP-complete problems (3-SAT, clique, vertex cover, graph colouring, Hamiltonian path, integer linear programming) under Karp reduction.
    • co-NP: the complement class of NP; contains problems whose “no” instances have polynomial-size witnesses. Tautology (complement of SAT) is co-NP-complete.
    • BPP: bounded-error probabilistic polynomial time; Randomised Algorithms with two-sided error bounded by 1/3. Believed to equal P under standard Derandomisation assumptions.
    • The polynomial hierarchy PH: a tower of classes Σ^P_k, Π^P_k, Δ^P_k extending P (Σ^P_0 = P) and NP (Σ^P_1 = NP); collapses to P if P = NP.
    • PSPACE (polynomial space): solvable in polynomial memory; contains NP and co-NP, and equals IP by Shamir’s theorem. PSPACE-complete problems arise in game tree evaluation, quantified Boolean formulae, and planning.
    • EXP and NEXP: deterministic and non-deterministic exponential time; strictly larger than PSPACE by the space and time hierarchy theorems.
    • Counting Complexity (#P): counting the number of accepting paths of a polynomial-time Turing Machine; P-complete problems include counting perfect matchings (Valiant, 1979), which is harder than NP even if P = NP.
  • Circuit Complexity
    • Boolean circuits model computation as directed acyclic graphs of AND, OR, and NOT gates; circuit size and depth correspond to sequential time and parallel time (NC and AC classes). Proving super-polynomial circuit lower bounds for explicit functions would separate P from NP, making circuit complexity central to the P vs NP programme. Classes NC^1, AC^0, TC^0 capture parallel computation; the separation AC^0 ⊊ TC^0 is known (parity not in AC^0), but NC^1 vs ACC^0 and ACC^0 vs TC^0 remain partially open.
  • Proof Complexity
    • Studies the minimal proof size required in formal proof systems (resolution, Frege, extended Frege) for tautologies; short proofs in all proof systems would imply NP ⊆ co-NP/poly. Connections to Derandomisation: if extended Frege proves derandomisation assumptions efficiently, then circuit lower bounds follow (2024 results connecting Proof Complexity and Circuit Complexity via Interactive Proofs).
  • Parameterised Complexity
    • Introduces a parameter k alongside input size n and seeks algorithms running in f(k)·n^c time (fixed-parameter tractable, FPT). The W-hierarchy characterises what cannot be made FPT. Practical for Constraint Satisfaction, bioinformatics network problems, and Knowledge Graph query answering.
  • Fine-Grained Complexity
    • Studies the exact time complexity of problems within P; e.g., the Strong Exponential Time Hypothesis (SETH) conjectures no O(2^{(1-ε)n}) algorithm for k-SAT and implies quadratic lower bounds for edit distance and other problems. Connects to algorithm design for sequences, graphs, and Data Structure problems. Recent work (2024–2025) has established robustness of SETH and equivalence classes among SETH variants (primal pathwidth SETH, W[P]-SETH, modulator-based variants), and extended fine-grained lower bounds to problems in abductive reasoning and propositional planning (IJCAI 2025).
  • Average-Case Complexity
    • Formalises computational hardness for random inputs from natural distributions, capturing the practical intractability relevant to Cryptography. Levin (1986) introduced distributional problems; average-case NP-hardness (DistNP-hardness) provides stronger evidence of practical intractability than worst-case results alone. Worst-case to average-case reductions for lattice problems (LWE, SIS) underpin all post-quantum Cryptographic Hardness Assumptions. The 2025 result connecting discrete logarithm speedups to k-SUM/k-CYC average-case equivalences illustrates the ongoing programme of placing cryptographic hardness on average-case complexity-theoretic foundations.
  • Communication Complexity
    • Studies the minimum number of bits two or more parties must exchange to compute a function of their distributed inputs; lower bounds in communication complexity imply circuit complexity lower bounds (via lifting theorems, extended in 2024 by Göös and colleagues). Serves as a bridge between practical network algorithm analysis and fundamental circuit complexity questions, and as a tool for proving lower bounds in Data Structure and Algorithm design.
  • Interactive Proofs and Hardness of Approximation
    • The PCP theorem (Arora, Lund, Motwani, Sudan, Szegedy, 1992–1998) shows NP = PCP(log n, 1) and implies that approximating MAX-3-SAT within 7/8+ε is NP-hard. Unique games conjecture (Khot, 2002) implies tight inapproximability for vertex cover, graph colouring, and many other Optimisation problems.

Canonical Benchmark Problems

  • SAT / 3-SAT: Prototype NP-complete problem (Cook, 1971); the input is a Boolean formula in conjunctive normal form and the question is whether any assignment of truth values to variables satisfies all clauses. Industrial SAT solvers (MiniSAT, CaDiCaL, Kissat) operating on DPLL/CDCL algorithms can routinely solve industrial-scale instances with millions of variables, but in theory no polynomial-time algorithm is known; random 3-SAT instances near the phase transition (clause-to-variable ratio ≈ 4.27) are hardest in practice. The 2024 SAT Competition (annual) provides standardised benchmarks and evaluates state-of-the-art solver performance.
  • Integer Factoring: Not known to be NP-complete but believed to be intractable for classical computers; Shor’s quantum algorithm (1994) solves it in polynomial time on a Quantum Computing device, making it the clearest complexity-theoretic separation between classical and quantum computation. Forms the foundation of RSA Cryptography.
  • Graph Colouring: Deciding if a graph is k-colourable is NP-complete for k ≥ 3; counting the number of proper 3-colourings is P-complete. Has applications in register allocation (compiler design), Constraint Satisfaction, and scheduling. Approximation algorithms for graph colouring are also hard: Zuckerman (2007) showed that for any ε > 0, approximating chromatic number within n^{1-ε} is NP-hard.
  • Travelling Salesman Problem (TSP): The decision version (is there a Hamiltonian cycle of weight ≤ k?) is NP-complete; the optimisation version (finding the minimum weight Hamiltonian cycle) is NP-hard. The Christofides-Serdyuk algorithm (1976) achieves a 3/2-approximation for metric TSP; the 2021 breakthrough by Karlin, Klein, and Oveis Gharan achieved 3/2 − ε for some ε > 0, a long-sought improvement. TSP is a flagship benchmark for Approximation Algorithms and Optimisation.
  • Quantified Boolean Formula (QBF): The canonical PSPACE-complete problem; decides whether a Boolean formula with alternating universal and existential quantifiers is true. Encodes two-player game tree evaluation, planning under adversarial conditions, and formal verification of concurrent systems. QBF solvers (DepQBF, CAQE) are increasingly used in formal Formal Verification and reactive synthesis pipelines.
  • Local Hamiltonian Problem: The QMA-complete problem (Kitaev, 1999); given a Hamiltonian (sum of local interaction terms) acting on n qubits, is the ground state energy below a given threshold? The quantum analogue of SAT, it underlies the study of quantum phase transitions, quantum chemistry simulation, and the computational complexity of Quantum Computing systems.
  • Graph Isomorphism: Given two graphs, are they structurally identical? Not known to be in P or NP-complete (a candidate for Ladner’s NP-intermediate class); Babai (2015, revised 2017) proved quasi-polynomial time algorithm (2^{O((log n)^3)}), a landmark result. Used in Knowledge Graph isomorphism testing, cheminformatics, and as a benchmark for the graph neural network expressivity literature.

Use Cases / Major Families

  • Cryptography and Security
    • Modern Cryptography rests entirely on complexity-theoretic hardness: the security of RSA, elliptic-curve cryptography, and post-quantum lattice-based cryptosystems (CRYSTALS-Kyber / ML-KEM, Dilithium / ML-DSA) reduces to the conjectured intractability of integer factorisation, discrete logarithm, and lattice shortest vector problems respectively. If P = NP, all of modern public-key Cryptography collapses — factoring would be solvable in polynomial time, discrete logarithm likewise, and the one-wayness that public-key cryptography depends on would be refuted. The development of post-quantum cryptography (NIST standards ML-KEM, ML-DSA, SLH-DSA finalised August 2024) is directly driven by the complexity-theoretic threat model posed by Quantum Computing (Shor’s algorithm runs in BQP, factoring in quantum polynomial time but not known classical polynomial time). Zero-knowledge proof systems — zk-SNARKs (Groth, 2016), STARKs (Ben-Sasson et al., 2018), PLONK (Gabizon et al., 2019) — provide cryptographic protocols where one party proves knowledge of a witness for an NP statement without revealing the witness; these rest on Interactive Proofs foundations and have become practically deployed in blockchain systems and AI auditing workflows. The complexity theory of zero-knowledge is rich: perfect zero-knowledge proof systems exist for all NP if one-way functions exist (Goldreich, Micali, Wigderson, 1986), and this connection between NP, one-way functions, and zero-knowledge is one of the deepest bridges between computational complexity and modern Cryptography. The 2024 NIST standards process and subsequent deployment planning across UK critical national infrastructure makes complexity-theoretic rigour in cryptographic hardness proofs directly relevant to national security engineering decisions.
  • Automated Reasoning and Ontology
    • Description Logic (the formal basis of OWL ontologies) has complexity determined by careful complexity-theoretic analysis: ALC concept satisfiability is PSPACE-complete; EL (used in SNOMED CT) is polynomial-time tractable; OWL DL is NEXPTIME-complete; the Horn-SHIQ fragment is P-complete. These characterisations guide the design of practical Ontology Reasoning systems (HermiT, Pellet, FaCT++, ELK for EL reasoning) and inform the tractability–expressivity tradeoffs in Knowledge Graph query answering. A 2024 result shows that answering queries from inconsistent DL-Lite Knowledge Graphs via universal consequence relation is NP-complete, motivating tractable approximations through techniques such as query rewriting and approximate reasoning algorithms. SPARQL query answering over OWL ontologies is generally undecidable for full OWL DL but decidable and tractable for specific fragments: answering conjunctive queries over DL-Lite ontologies is LOGSPACE-complete (tractable in data complexity), making DL-Lite the preferred language for large Knowledge Graph deployments such as Wikidata, Freebase-derived graphs, and enterprise ontology systems. The interplay between Parameterised Complexity and Knowledge Graph query evaluation has become an active research area: treewidth-parameterised complexity analysis identifies structural properties of Knowledge Graphs that make otherwise intractable queries tractable in practice, with fixed-parameter tractable algorithms for acyclic conjunctive queries and bounded-treewidth inputs. The Automated Reasoning community increasingly uses SAT Solving (DPLL-based, CDCL solvers) and Constraint Satisfaction technology as backends for decidable fragment reasoning, particularly for planning, temporal logic model checking, and bounded model verification, all of which have precise complexity characterisations that inform tool and algorithm selection.
  • Constraint Satisfaction and Optimisation
    • Constraint Satisfaction problems (CSP), including graph colouring, timetabling, and resource allocation, are classified by the Feder-Vardi dichotomy theorem (proved by Bulatov and Zhuk in 2017): every finite-domain CSP is either in P or NP-complete. This complexity classification guides the selection of solvers (propagation, DPLL-based SAT Solving, Approximation Algorithms) for practical Optimisation.
  • Machine Learning Theory
    • Computational Learning Theory uses complexity-theoretic reductions to prove that certain concept classes (e.g., sparse polynomial threshold functions) are not efficiently PAC-learnable unless RP = NP, and that training Neural Networks to global optimality is NP-hard (Blum and Rivest, 1992; many follow-ups). Conversely, recent work (2024) on learning one-hidden-layer Neural Networks with Gaussian inputs identifies polynomial-time learnable subclasses, demonstrating productive interplay between complexity theory and Machine Learning practice. A major 2024 result at NeurIPS established a fine-grained complexity result for gradient computation in attention mechanism evaluation — the attention matrix-vector product, central to Large Language Models and Transformer architectures, cannot be computed significantly faster than O(n^2) in the worst case without violating SETH, providing the first complexity-theoretic lower bound for a fundamental operation in Deep Learning. This connects the theoretical complexity programme directly to the engineering constraints of scaling Machine Learning systems. The broader Computational Learning Theory programme also characterises the sample complexity of learning — how many examples are needed for PAC learning — through VC dimension and Rademacher complexity, and characterises when distribution shift (covariate shift, concept drift) makes learning provably harder; these results are increasingly relevant to the deployment of Machine Learning in regulated domains (medical, financial, legal) where robustness under distribution shift is a safety requirement.
    • The complexity of neural network verification — determining whether a trained Neural Network satisfies a given property (e.g., robustness to perturbations, absence of fairness violations) — has been studied intensively: complete verification is co-NP-hard even for ReLU networks with one hidden layer (Katz et al. 2017), and scales exponentially in the worst case. This motivates the development of sound-but-incomplete verification tools (linear relaxation, abstract interpretation) and has stimulated complexity-theoretic research into efficiently verifiable properties of Neural Networks and what abstraction granularity is needed to maintain completeness within tractable complexity bounds.
  • Quantum Complexity
    • The class BQP (bounded-error quantum polynomial time) captures what Quantum Computing can efficiently solve: integer factoring (Shor, 1994), discrete logarithm, and simulation of quantum systems (Lloyd, 1996). The relationship BQP ⊆ PSPACE is known; it is conjectured (but unproved) that BQP ⊄ NP and NP ⊄ BQP (i.e., quantum computers likely do not solve all NP problems efficiently). The class QMA (quantum Merlin-Arthur) captures quantum NP; the local Hamiltonian problem is QMA-complete (Kitaev, 1999). Google’s 105-qubit Willow processor (2024) demonstrated below-threshold error correction — a prerequisite for fault-tolerant quantum computation relevant to BQP-class problems. The first QCOW (Quantum Cambridge-Oxford-Warwick Colloquium, Oxford, December 2025) focused on quantum low-depth complexity, exploring the boundary between constant-depth quantum circuits (QNC^0) and classical constant-depth circuits (AC^0, TC^0), where quantum advantage is achievable for certain relational problems even without fault tolerance. Quantum complexity theory is increasingly relevant to Cryptography as the transition to post-quantum algorithms (ML-KEM, ML-DSA, SLH-DSA in NIST standards 2024) must be grounded in hardness assumptions that are robust against quantum adversaries: learning with errors (LWE) is not known to be in BQP, and worst-case hardness results for lattice problems under quantum reduction chains are the subject of ongoing research by the UK NCSC, GCHQ, and academic cryptographers at Royal Holloway (Information Security Group), Bristol, and Edinburgh. The complexity-theoretic understanding of what quantum computers can and cannot do efficiently will determine the long-term security of digital infrastructure as quantum hardware continues to scale through 2026–2030.

Academic Context

  • The formal origins of computational complexity theory are dated to the 1960s: Hartmanis and Stearns (1965) introduced the time complexity of computable functions and proved the time hierarchy theorem. Cook (1971) proved that Boolean satisfiability (Boolean Satisfiability, SAT) is NP-complete; Karp (1972) showed 21 combinatorial problems are NP-complete under polynomial reductions, establishing the field’s combinatorial identity. Ladner (1975) proved that if P ≠ NP, there exist problems strictly between P and NP-complete (Ladner’s theorem). Savitch (1970) proved NSPACE(f(n)) ⊆ DSPACE(f(n)^2); Immerman and Szelepcsényi (1988) proved NL = co-NL. Valiant (1979) introduced the permanent and the class P; his 1984 PAC learning framework launched Computational Learning Theory. The PCP theorem (Arora et al., 1992–1998) was named “breakthrough of the decade” by the AMS. Razborov and Rudich (1994) identified the natural proofs barrier, explaining why most circuit lower bound techniques cannot resolve P vs NP. Reingold (2008) proved undirected graph connectivity is in L (logarithmic space), a major result separating algorithmic insight from resource requirements. Impagliazzo, Paturi, and Zane (2001) introduced the ETH and SETH hypotheses that launched the Fine-Grained Complexity programme. Williams (2010) proved ACC^0 ≠ NEXP, the first circuit lower bound against a non-trivial circuit class in decades. The Feder-Vardi dichotomy for CSPs, conjectured in 1993, was proved independently by Bulatov (2017) and Zhuk (2020) — one of the most celebrated recent results in complexity. Geometric complexity theory (Mulmuley and Sohoni, 2001 and subsequent) attempts to separate permanent from determinant via algebraic geometry and representation theory, potentially resolving VP vs VNP (the algebraic analogue of P vs NP). Key monographs include Garey and Johnson (1979) “Computers and Intractability”, Papadimitriou (1994) “Computational Complexity”, and Arora and Barak (2009) “Computational Complexity: A Modern Approach”. The Computational Complexity Foundation’s Complexity blog (Fortnow and Gasarch), the ECCC (Electronic Colloquium on Computational Complexity), and the annual CCC (Conference on Computational Complexity) and STOC/FOCS are the primary publication venues. The Oxford-Warwick Complexity Meetings (ongoing, 2024–2026) provide a regular UK forum for complexity research discussions, while the first Quantum Cambridge-Oxford-Warwick Colloquium (QCOW, December 2025) focused specifically on quantum low-depth complexity, reflecting the growing intersection of quantum computation and classical complexity theory.

Current Landscape (2026)

  • Computational complexity research in 2025–2026 is characterised by three major thrusts:
  • Space complexity breakthroughs: Williams (2025) advanced space-efficient simulation of time-bounded computation; Cook and Mertz (2024) gave a log-space Algorithm for Tree Evaluation, settling a long-open problem and inspiring work on catalytic computing (computation that temporarily uses work tape containing useful data that must be restored). These results suggest that the gap between time and space complexity is smaller than previously believed.
  • Derandomisation and Circuit Complexity lower bounds: A 2024 paper at ICALP (Göös and colleagues) connected Proof Complexity and Circuit Complexity via Interactive Proofs, showing that if a proof system efficiently formalises derandomisation assumptions, then superpolynomial Proof Complexity lower bounds imply PSPACE ⊄ P/poly. Igor Carboni Oliveira (Warwick) presented work on meta-mathematics of computational complexity and probabilistic polynomial-time reasoning at multiple venues in 2024–2025, extending the programme of proving circuit lower bounds via meta-mathematical arguments.
  • P vs NP in 2025: The annual computational complexity blog “Year in Review” (Fortnow, 2025) noted an intensification of P vs NP proof attempts; a December 2025 Mathematics journal paper approached the question via time-relative description complexity and epistemic barriers, arguing that even if polynomial-time algorithms for NP-complete problems exist, their minimal descriptions may have very high Kolmogorov complexity, making them practically undiscoverable. The Clay Mathematics Institute hosted a 2025 April workshop “P vs NP and Complexity Lower Bounds” bringing together leading researchers.
  • Quantum Computing and complexity: As IBM’s Heron processor (133 qubits, 2024) and Fujitsu/RIKEN’s 256-qubit superconducting computer (April 2025) push qubit counts, the complexity-theoretic question of what advantage quantum computation provides over classical computation is increasingly urgent. Google’s Willow processor demonstrated exponential error suppression as qubit arrays grow, realising the “below threshold” regime for surface-code error correction — a prerequisite for running Shor’s algorithm on cryptographically relevant instances.
  • Complexity and Machine Learning: The question of when Deep Learning optimisation is computationally tractable or hard is receiving formal complexity-theoretic treatment: results in 2024 established NP-hardness for learning one hidden layer Neural Networks under worst-case input distributions, while characterising efficiently learnable regimes. The interface between Computational Learning Theory and Deep Learning practice remains one of the most active and practically consequential areas of research.
  • Ontology Reasoning and knowledge tractability: Oxford’s 2025–2026 Computational Complexity course and Cambridge’s Complexity Theory curriculum both now include Description Logic tractability as a significant topic, reflecting the practical importance of complexity-theoretic analysis for Ontology design in large-scale Knowledge Graph deployment. The Warwick Algebraic Complexity, Geometry, and Representations workshop (2024–2025) brought together researchers in GCT and arithmetic complexity, formalising connections between moment polytope computation and permanent-determinant separation that could advance the VP vs VNP problem — the algebraic analogue of P vs NP over fields. The Parameterised Complexity community, centred at TU Wien (Szeider), Utrecht (Bodlaender), and Warsaw (Pilipczuk), continued active work on kernelisation — determining when NP-hard problems have polynomial kernels parameterised by structural parameters such as treewidth, feedback vertex set size, and modular width — with applications to fixed-parameter tractable Algorithm design for bioinformatics, network analysis, and Knowledge Graph query evaluation.
  • Ryan Williams’s breakthroughs in space complexity and pseudorandomness (2025): Williams’s 2025 results on pseudorandomness and constructive Ramsey theory, cited by Fortnow as a highlight of the year, advanced the programme connecting derandomisation with Circuit Complexity lower bounds. These results build on Williams’s foundational ACC^0 lower bound (2010) that showed NEXP ⊄ ACC^0, still one of the few unconditional circuit lower bounds proved in decades, and establish new connections between the pseudorandomness needed for Derandomisation and the explicit constructions needed for combinatorics.

UK Context

  • The United Kingdom has strong institutional presence in computational complexity research. The Cambridge Department of Computer Science and Technology offers a dedicated Complexity Theory course (2024–25 and 2025–26) covering NP-completeness, space complexity classes, hierarchy theorems, Randomised Algorithms, quantum complexity, and Interactive Proofs; the annual Cambridge Algorithms and Complexity Workshop (CACW, first held April 2024) brings together UK and international speakers on Theoretical Computer Science topics including the Nisan-Ronen conjecture and FPRAS Approximation Algorithms. Oxford’s Department of Computer Science similarly offers computational complexity in both undergraduate and graduate curricula; Elias Koutsoupias (Oxford) has presented at the CACW on algorithmic game theory and complexity. The Quantum Cambridge-Oxford-Warwick Colloquium (QCOW), inaugurated at Oxford in December 2025, focuses specifically on quantum low-depth complexity, bringing together researchers from all three institutions to advance the intersection of quantum algorithms and classical Circuit Complexity lower bounds.
  • Warwick University’s Department of Computer Science hosts Igor Carboni Oliveira, one of the most active young researchers in proof and circuit complexity internationally, who has presented recent work on probabilistic polynomial-time reasoning and P vs NP at multiple venues in 2024–2025. Warwick’s Oxford-Warwick Complexity Meetings (online, ongoing 2024–2026) provide a regular informal forum for complexity research discussions. Warwick also hosted the “Algebraic Complexity, Geometry, and Representations” workshop in 2024–2025, connecting geometric complexity theory with representation theory and practical numerical optimisation. Edinburgh’s Heng Guo presented FPRAS (fully polynomial randomised approximation scheme) results at the CACW 2024, reflecting Edinburgh’s strength in counting complexity and approximate counting via the correlation decay method for partition functions. Edinburgh has an active theoretical computer science group with further strengths in algorithmic Information Theory, logic in computer science, and parameterised complexity applied to bioinformatics network problems. Imperial College London hosts Iddo Tzameret, who has made significant contributions to Proof Complexity and the theory of Randomised Algorithms, with postdoctoral positions advertised in 2024–2025 for complexity theory research. The Alan Turing Institute in London, named after the founding theorist of computability and complexity, convenes interdisciplinary research that connects complexity theory with Machine Learning, Cryptography, and formal verification — including the Turing’s Safe and Ethical AI programme and Turing’s Cyber Security programme, both of which depend on complexity-theoretic foundations.
  • The UK government’s National Cyber Security Centre (NCSC) tracks complexity-theoretic developments — particularly the quantum threat to RSA and elliptic-curve Cryptography — and has co-ordinated the UK’s transition to post-quantum Cryptography (NIST-standardised algorithms in 2024) in parallel with GCHQ and national critical infrastructure operators. The post-quantum cryptography standards (ML-KEM / CRYSTALS-Kyber for key encapsulation, ML-DSA / CRYSTALS-Dilithium for signatures) all rest on lattice hardness assumptions — Learning With Errors (LWE), Shortest Integer Solution (SIS) — that are the subject of active complexity-theoretic research in worst-case to average-case reductions. The UK Cyber Security Council’s 2025 strategy document explicitly references lattice-based Cryptographic Hardness Assumptions as the foundation of long-term security planning. In Northern England, the University of Manchester’s department of Mathematics engages with combinatorial complexity through extremal graph theory and Ramsey theory connections, while Sheffield and Leeds have representation in algorithms and Data Structure efficiency research through their computer science departments. The complexity theory community is relatively concentrated at the research-intensive universities — Cambridge, Oxford, Warwick, Edinburgh, Imperial — but undergraduate education in computational complexity reaches students at all UK universities through CS curricula mandated by BCS (British Computer Society) accreditation requirements, ensuring that appreciation of tractability and hardness boundaries is embedded in the UK computing workforce.

Future Directions (2026–2030)

  • Resolving the P vs NP question: While no expert consensus exists on when or if P vs NP will be resolved, new approaches — geometric complexity theory (Mulmuley and Sohoni), algebraic approaches via permanent vs determinant, and meta-mathematical analysis via Kolmogorov Complexity — are being pursued in parallel. The April 2025 Clay Mathematics Institute workshop “P vs NP and Complexity Lower Bounds” brought together leading researchers exploring epistemic barriers and description-complexity approaches. A resolution, even partial (e.g., proving circuit lower bounds that imply P ≠ NP relative to all oracles), would be one of the most significant mathematical breakthroughs in history and would immediately reshape Cryptography, Artificial Intelligence, Optimisation, and Knowledge Representation.
  • Quantum advantage characterisation: As fault-tolerant Quantum Computing approaches feasibility (IBM targets 200 logical qubits by 2028 in the Starling system; Fujitsu/RIKEN’s 256-qubit superconducting processor reached operational status in April 2025), the boundary between BQP and classical polynomial time will be empirically probed at increasing scale. Complexity-theoretic analysis of structured problems (dequantisation results for quantum-inspired classical algorithms — Tang 2018, Chia et al. 2020 — quantum walk algorithms for Graph Algorithms, and quantum simulation of physical systems) will clarify where quantum advantage is genuine versus reproducible classically.
  • Fine-grained complexity and Algorithm design: The SETH-based conditional lower-bound programme will continue to identify tight complexity barriers for problems in sequence analysis, Graph Algorithms, and Data Structure operations, driving the design of algorithms that provably match these bounds. The 2025 extension of fine-grained lower bounds to propositional abduction (IJCAI 2025) and to k-SUM/k-CYC connections for cryptographic average-case complexity illustrates the expanding scope of the programme.
  • Complexity of Deep Learning: Formal understanding of why stochastic gradient descent finds good minima in practice despite worst-case NP-hardness training results will require new complexity-theoretic tools from Average-Case Complexity, Randomised Algorithms, and smoothed analysis — probabilistic analysis of algorithm performance on random perturbations of worst-case inputs (Spielman and Teng, 2004). This is the central open problem at the intersection of Machine Learning and computational complexity, with implications for understanding the practical trainability of Neural Networks and the foundations of Deep Learning.
  • Proof complexity and circuit lower bounds: The 2024 programme connecting Proof Complexity and Circuit Complexity via Interactive Proofs (Göös et al., ICALP 2024) opens a new route to proving circuit lower bounds: if proof systems efficiently formalise Derandomisation assumptions, lower bounds for proof size imply circuit lower bounds. This approach avoids the natural proofs barrier and may represent the most promising near-term route to unconditional P ≠ NP results.
  • Complexity and privacy: Differential privacy, secure multi-party computation, and zero-knowledge proofs all rest on complexity-theoretic hardness assumptions; as Machine Learning is applied at population scale in healthcare and finance, the complexity foundations of privacy-preserving computation will receive increasing theoretical and regulatory attention. The interface between Post-Quantum Cryptography, zero-knowledge proof systems (zk-SNARKs, STARK protocols), and formal complexity characterisations is an active area with direct implications for blockchain, privacy law compliance, and AI auditing frameworks.
  • Complexity and formal AI verification: As regulators (EU AI Act, UK AI Safety Institute) increasingly require formal guarantees about AI system behaviour, the complexity of verifying properties of Neural Networks and Deep Learning systems becomes practically critical. Results showing that neural network verification is co-NP-hard even for simple properties (Katz et al., 2017; Ehlers, 2017) establish fundamental barriers, motivating the search for tractable verification subclasses and efficiently verifiable safety certificates that are robust under small input perturbations.
  • Algebraic and geometric complexity: Geometric complexity theory (GCT) via representation theory and algebraic geometry, and related approaches through arithmetic Circuit Complexity (VP vs VNP), offer mathematically mature frameworks for separating complexity classes in algebraic computation models. Advances in moment polytope computation (Warwick, 2024–2025) connect these to practical numerical linear algebra and are building towards the algebraic underpinnings needed for GCT-based separations.

Key Terminology Glossary

  • P: Class of decision problems solvable by a deterministic Turing Machine in polynomial time; informally “efficiently solvable.”
  • NP: Class of decision problems verifiable in polynomial time; contains all NP-complete problems. P ⊆ NP, but whether P = NP is unknown.
  • NP-complete: A problem is NP-complete if it is in NP and every NP problem reduces to it in polynomial time; the “hardest” NP problems. SAT (Cook-Levin) was the first; Karp identified 21 more.
  • PSPACE: Problems solvable in polynomial space; contains P, NP, co-NP; equals IP (Shamir, 1992).
  • BPP: Bounded-error probabilistic polynomial time; problems solvable by Randomised Algorithms with error probability ≤ 1/3; believed to equal P under Derandomisation assumptions.
  • P: The class of counting problems corresponding to NP decision problems; P-complete problems (counting perfect matchings, Valiant 1979) are computationally harder than NP in a precise sense.
  • BQP: Bounded-error quantum polynomial time; the class of problems efficiently solvable on a Quantum Computing device; integer factoring (Shor 1994) is in BQP but not known to be in P or NP.
  • ETH / SETH: The (Strong) Exponential Time Hypothesis posits that k-SAT requires exponential time near 2^n; used in Fine-Grained Complexity to derive tight conditional lower bounds for problems within P such as edit distance and longest common subsequence.
  • Polynomial-time reduction (Karp reduction): A many-one function mapping instances of problem A to instances of problem B in polynomial time, preserving yes/no answers; used to transfer hardness.
  • Oracle: An idealised subroutine that answers membership queries in one step; oracle separations show certain proof techniques cannot resolve P vs NP.
  • PCP theorem: Every NP proof can be probabilistically verified by reading O(log n) random bits and a constant number of proof symbols; implies hardness of approximation.
  • Circuit complexity: Study of Boolean circuits (DAGs of logic gates) as an alternative computation model; proving super-polynomial lower bounds for explicit functions is a central open problem.
  • Time hierarchy theorem: For t(n) > s(n) log s(n), DTIME(s(n)) ⊊ DTIME(t(n)); more time yields strictly more computational power.
  • Average-case complexity: The study of problem hardness under a probability distribution over inputs; more practically relevant than worst-case complexity for applications in Cryptography where inputs are drawn from natural distributions.
  • Unique Games Conjecture (UGC): Khot (2002) conjectured that a certain 2-player constraint satisfaction problem (Unique Games) is NP-hard to approximate better than trivially; the conjecture implies tight inapproximability results for vertex cover, Max-Cut, and other Optimisation problems, and remains one of the most important open problems in the PCP/hardness of approximation programme.
  • Geometric Complexity Theory (GCT): Mulmuley and Sohoni’s programme using algebraic geometry and representation theory to attack permanent vs determinant and VP vs VNP; aims to prove circuit complexity lower bounds via symmetry arguments without encountering the natural proofs barrier.
  • Relativisation / Oracle separation: Baker, Gill, Solovay (1975) showed there exist oracles A, B such that P^A = NP^A and P^B ≠ NP^B, meaning simple diagonalisation arguments cannot resolve P vs NP; this identified the relativisation barrier.

Research & Literature

Provenance

Graph View

Backlinks