Complexity is a phenomenon that has two distinct and almost opposite meanings. The first, and probably the oldest mathematically, goes back to Andrei Kolmogorov's attempt to give an algorithmic foundation to notions of randomness and probability and to Claude Shannon's study of communication channels via his notion of information. In both cases, complexity is synonymous with disorder and a lack of structure. The more random a process is, the greater its complexity. An ideal gas, for example, with its numerous molecules bouncing around in complete disarray, is complex as far as Kolmogorov and Shannon are concerned. Thus, in this sense, complexity equates to the degree of complication. It is with this aspect of complexity that complexity theory in computer science is involved.

 

The second, and more recent notion of "complexity" refers instead to how structured, intricate, hierarchical, and sophisticated a natural process is. In particular, it's a property associated with dynamical systems in which new, unpredictable behavior arises on scales above the level of the constituent components. The distinction between these two meanings can be revealed by answering a simple question about a system: Is it complex or is it merely complicated? Measures of complexity include algorithmic complexity, fractal dimensionality, Lyapunov exponents, and logical depth.

 

Complexity theory

Complexity theory is a part of the theory of computation that has to with the resources needed to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem). Complexity theory differs from computability theory, which deals with whether a problem can be solved at all, regardless of the resources required.