Computational complexity theory is a branch of the theory of computation in computer science that focuses on classifying problems according to their inherent difficulty. Here, a problem is understood in the narrow sense of a task that is in principle amenable to be solved by a computer. Informally, a problem is regarded as inherently difficult if solving the problem requires a large amount of resources, independent of the algorithm used for solving it. The theory formalizes this intuition, by introducing mathematical models of computation and casting computational tasks mathematically as decision problems. The degree of difficulty can be quantified in the amount of resources needed to solve these problems, such as time and storage. In particular, the theory seizes the practical limits on what computers can and cannot do.

Neighboring fields of study inside theoretical computer science are analysis of algorithms and computability theory. A key distinction between computational complexity theory and analysis of algorithm is that the latter is devoted on analyzing the amount of resources needed by a particular algorithm to solve a concrete problem, whereas the former asks a more general question. Namely, it targets at classifying problems that can, or cannot, be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources distinguishes computational complexity from computability theory: the latter asks what kind of problems can be solved at all (within a given computational model).