Complexity
From NECSIWiki
Complexity is sometimes used to refer to the general concept of complex systems. Here we focus on quantitative definitions of a measure of systems that characterizes them. A measure is something that can address the question "How complex is it?" Frequently such measures are defined for mathematical entities rather than physical ones.
Contents |
[edit] Quantitative definitions of complexity
Complexity is ...[the abstract notion of complexity has been captured in many different ways. Most, if not all of these, are related to each other and they fall into two classes of definitions]:
- ...the (minimal) length of a description of the system.
- ...the (minimal) amount of time it takes to create the system.
The length of a description is measured in units of information (for a given resolution). The former definition is closely related to Shannon information theory and algorithmic complexity, and the latter is related to computational complexity.
[edit] Descriptive complexity
The length of a description of the system. Formally description length is measured by information as defined by Shannon.
[edit] Computational complexity
The scaling of computational time of an algorithm as a function of the problem size.
[edit] Algorithmic complexity
Also known as Kolmogorov complexity.
Given a string of (binary) characters. The Algorithmic complexity is the length of the shortest computer program (in the sense of Turing) that generates the string.
[edit] Related concepts:
description, information, algorithmic complexity, computational complexity, emergence and complexity, emergence, complexity profile, self-organization
