Studiet av hvor vanskelige problemer er. ### Kompleksitetsklasser - [[P]] - [[NP]] - [[coNP]] - [[NP snitt coNP]] - [[BPP]] - [[BQP]] - [[QMA]] - [[QMA-NP]] - [[distNP]] - [[PSPACE]] - [[EXP]] ### Annet - [[Impagliazzos fem verdener]] - [[Kolmogorov-kompleksitet]] - [[PCP-teoremet]] ### Litteratur - [[Quantum Computing Since Democritus]], semi-populærvitenskapelig bok om kompleksitetsteori av [[Scott Aaronson]] (som tross alt er, blant mye annet, først og fremst en kompleksitetsteoretiker).