Computational complexity is the branch of theoretical computer science that asks not whether a problem can be solved, but at what cost. The Stanford Encyclopedia of Philosophy describes how complexity theory classifies computable problems into “computational complexity classes according to how much computation” is needed to solve them - typically measured as the amount of time or memory an algorithm uses as a function of the size of its input.
This makes complexity distinct from computability. Computability asks only the yes-or-no question of whether a problem is solvable in principle by a computing device. Complexity assumes a problem is solvable and then asks how expensive that solution is in practice. A problem can be perfectly computable yet remain intractable because every known algorithm for it requires an impractical amount of time.
The Stanford Encyclopedia notes the standard chain of inclusions among the main classes - P is contained in NP, which is contained in PSPACE, which is contained in EXPTIME - while observing that almost none of the suspected separations between these classes has actually been proved. The only proper inclusion known from that chain is that P is strictly smaller than EXPTIME.
The field’s foundational results came in the early 1970s. Stephen Cook’s 1971 paper “The Complexity of Theorem-Proving Procedures” introduced the idea of reducing one problem to another within polynomial time and used it to identify a hardest class of problems inside NP, launching decades of work on classifying problems by difficulty.