Computational Complexity
Computational complexity is the branch of theoretical computer science that classifies computational problems by the amount of resources — typically time or memory — required to solve them as input size grows.
Definition
Computational complexity is the branch of theoretical computer science that classifies computational problems by the amount of resources — typically time or memory — required to solve them as input size grows.
Overview
Computational complexity theory asks not just whether a problem can be solved, but how efficiently. Algorithms are classified using Big O Notation-style asymptotic analysis, describing how running time or memory usage scales as input size increases — for example, sorting algorithms typically run in O(n log n) time, while naive matrix multiplication runs in O(n³). Beyond analyzing individual algorithms, complexity theory groups entire problems into complexity classes based on the resources any algorithm would need to solve them. The most famous classes are P (problems solvable in polynomial time) and NP (problems whose proposed solutions can be verified in polynomial time). Problems that are provably as hard as any other problem in NP are called NP-Complete Problems, and whether P equals NP remains one of the field's central open questions. Other important classes include PSPACE (solvable using polynomial memory regardless of time) and undecidable problems — those no algorithm can solve at all, as proven for the Halting Problem using a Turing Machine as the formal model of computation. Computational complexity guides real engineering decisions: recognizing that a problem is NP-complete tells a developer to look for approximations rather than exact efficient solutions; understanding an algorithm's time complexity determines whether it will scale to production data volumes. The field connects deeply to cryptography, where the security of many systems rests on the assumed hardness of specific computational problems, and to algorithm design more broadly, where trade-offs between time, memory, and accuracy are constantly weighed.
Key Concepts
- Classifies problems and algorithms by required time or memory as input size grows
- Uses asymptotic (Big O-style) notation to describe scaling behavior
- Defines complexity classes such as P, NP, NP-complete, and PSPACE
- Distinguishes decidable problems from undecidable ones, like the Halting Problem
- Central open question: whether P equals NP
- Grounded formally in the Turing machine model of computation
- Guides practical algorithm selection and system scalability decisions
- Underpins cryptographic security assumptions about problem hardness