Complexity Class

A **complexity class** is a set of computational problems sharing related resource requirements — typically time or memory — measured on a fixed model of computation. ## The Turing machine model Classes are defined using the Turing machine, which abstracts time as the number of elementary steps and space as the number of tape cells used, making the analysis independent of physical hardware. A **deterministic** machine (DTM) follows fixed rules; a **nondeterministic** machine (NTM) may explore multiple branches at once. Most classes concern decision problems (yes/no answers). ## Key classes - **P**: solvable by a DTM in polynomial time — the standard notion of 'efficiently solvable'. - **NP**: solvable by an NTM in polynomial time; equivalently, solutions verifiable by a DTM in polynomial time. - **co-NP**: problems whose *no*-instances have polynomial-time-verifiable certificates (the complements of NP problems). - **PSPACE**: solvable in polynomial space; Savitch's theorem gives PSPACE = NPSPACE. - **EXPTIME**: solvable by a DTM in exponential time. ## Known hierarchy The established inclusions are L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE. Many of these inclusions are not known to be strict — most famously whether P = NP. ## Asymptotic measurement Complexity classes are about the *rate of growth* of required resources as input size increases, expressed with Big O notation, classifying families of growth functions rather than exact runtimes. See Why Complexity Is Measured Asymptotically, Not by Counting Steps.