Editing Theoretical computer science (section)

===Computational complexity theory===
{{main|Computational complexity theory}}
[[Computational complexity theory]] is a branch of the [[theory of computation]] that focuses on classifying [[computational problems]] according to their inherent difficulty, and relating those [[Complexity class|classes]] to each other. A computational problem is understood to be a task that is in principle amenable to being solved by a computer, which is equivalent to stating that the problem may be solved by mechanical application of mathematical steps, such as an [[algorithm]].

A problem is regarded as inherently difficult if its solution requires significant resources, whatever the [[algorithm]] used. The theory formalizes this intuition, by introducing mathematical [[models of computation]] to study these problems and quantifying the amount of resources needed to solve them, such as time and storage. Other [[complexity]] measures are also used, such as the amount of communication (used in [[communication complexity]]), the number of [[logic gate|gates]] in a circuit (used in [[circuit complexity]]) and the number of processors (used in [[parallel computing]]). One of the roles of computational complexity theory is to determine the practical limits on what [[computer]]s can and cannot do.