Computational complexity theory

Summary

Computational complexity theory studies how much of a resource, such as time or memory, is needed to solve a computational problem. The amount is measured as a function of the size of the input. It measures problems by the best algorithm for them, not by one particular algorithm. Problems with similar needs are grouped into complexity classes such as P and NP, which are compared by reductions. Its central open question is the P versus NP problem.