Editing Complexity (section)

== Varied meanings ==
{{see also|:Category:Measures of complexity}}
In several scientific fields, "complexity" has a precise meaning:

* In [[computational complexity theory]], the [[Computational resource|amounts of resources]] required for the execution of [[algorithm]]s is studied. The most popular types of computational complexity are the time complexity of a problem equal to the number of steps that it takes to solve an instance of the problem as a function of the [[problem size|size of the input]] (usually measured in [[Bit|bits]]), using the most efficient [[algorithm]], and the space complexity of a problem equal to the volume of the [[computer storage|memory]] used by the algorithm (e.g., cells of the tape) that it takes to solve an instance of the problem as a function of the size of the input (usually measured in bits), using the most efficient algorithm. This allows classification of computational problems by [[complexity class]] (such as [[P (complexity)|P]], [[NP (complexity)|NP]], etc.). An [[Axiomatic system|axiomatic]] approach to computational complexity was developed by [[Manuel Blum]]. It allows one to deduce many properties of concrete computational complexity measures, such as time complexity or space complexity, from properties of axiomatically defined measures.
* In [[algorithmic information theory]], the ''[[Kolmogorov complexity]]'' (also called ''descriptive complexity'', ''algorithmic complexity'' or ''algorithmic [[Entropy (information theory)|entropy]]'') of a [[string (computer science)|string]] is the length of the shortest binary [[computer program|program]] that outputs that string. [[Minimum message length]] is a practical application of this approach. Different kinds of Kolmogorov complexity are studied: the uniform complexity, prefix complexity, monotone complexity, time-bounded Kolmogorov complexity, and space-bounded Kolmogorov complexity. An axiomatic approach to Kolmogorov complexity based on [[Blum axioms]] (Blum 1967) was introduced by Mark Burgin in the paper presented for publication by [[Andrey Kolmogorov]].<ref>Burgin, M. (1982) Generalized Kolmogorov complexity and duality in theory of computations, Notices of the Russian Academy of Sciences, v.25, No. 3, pp. 19–23</ref> The axiomatic approach encompasses other approaches to Kolmogorov complexity. It is possible to treat different kinds of Kolmogorov complexity as particular cases of axiomatically defined generalized Kolmogorov complexity. Instead of proving similar [[Theorem|theorems]], such as the basic invariance theorem, for each particular measure, it is possible to easily deduce all such results from one corresponding theorem proved in the axiomatic setting. This is a general advantage of the axiomatic approach in [[mathematics]]. The axiomatic approach to Kolmogorov complexity was further developed in the book (Burgin 2005) and applied to software metrics (Burgin and Debnath, 2003; Debnath and Burgin, 2003).
*In [[information theory]], [[information fluctuation complexity]] is the fluctuation of information about [[Entropy (information theory)|information entropy]]. It is derivable from fluctuations in the predominance of order and chaos in a dynamic system and has been used as a measure of complexity in many diverse fields.
* In [[Data processing|information processing]], complexity is a measure of the total number of [[property|properties]] transmitted by an object and detected by an [[observation|observer]]. Such a collection of properties is often referred to as a [[state (computer science)|state]].
* In [[physical systems]], complexity is a measure of the [[probability]] of the [[Quantum state|state vector]] of the system. This should not be confused with [[entropy (statistical thermodynamics)|entropy]]; it is a distinct mathematical measure, one in which two distinct states are never conflated and considered equal, as is done for the notion of entropy in [[statistical mechanics]].
* In [[dynamical systems]], statistical complexity measures the size of the minimum program able to statistically reproduce the patterns (configurations) contained in the data set (sequence).<ref>{{Cite journal |last1=Crutchfield |first1=J.P. |last2=Young |first2=K. |year=1989 |title=Inferring statistical complexity |journal=[[Physical Review Letters]] |volume=63 |issue=2 |pages=105–108|doi=10.1103/PhysRevLett.63.105 |pmid=10040781 |bibcode=1989PhRvL..63..105C }}</ref><ref>{{Cite journal |last1=Crutchfield |first1=J.P. |last2=Shalizi |first2=C.R. |year=1999
 |title=Thermodynamic depth of causal states: Objective complexity via minimal representations |journal=[[Physical Review E]] |volume=59 |issue=1 |pages=275–283
|doi=10.1103/PhysRevE.59.275 |bibcode=1999PhRvE..59..275C }}</ref> While the algorithmic complexity implies a deterministic description of an object (it measures the information content of an individual sequence), the statistical complexity, like [[forecasting complexity]],<ref>{{cite journal |last1=Grassberger |first1=P. |year=1986 |title=Toward a quantitative theory of self-generated complexity |journal=[[International Journal of Theoretical Physics]] |volume=25 |issue=9 |pages=907–938 |doi=10.1007/bf00668821|bibcode=1986IJTP...25..907G|s2cid=16952432 }}</ref> implies a statistical description, and refers to an ensemble of sequences generated by a certain source. Formally, the statistical complexity reconstructs a minimal model comprising the collection of all histories sharing a similar probabilistic future and measures the [[entropy (information theory)|entropy]] of the probability distribution of the states within this model. It is a computable and observer-independent measure based only on the internal dynamics of the system and has been used in studies of emergence and self-organization.<ref>{{cite journal
 |last1=Prokopenko |first1=M. |last2=Boschetti |first2=F. |last3=Ryan |first3=A. |year=2009 |title=An information-theoretic primer on complexity, self-organisation and emergence |journal=Complexity |volume=15 |issue=1 |pages=11–28 |doi=10.1002/cplx.20249 |bibcode=2009Cmplx..15a..11P }}</ref> 
* In [[mathematics]], [[Krohn–Rhodes complexity]] is an important topic in the study of finite [[semigroup]]s and [[automata theory|automata]].
* In [[network theory]], complexity is the product of richness in the connections between components of a system,<ref>A complex network analysis example: "[http://www.martingrandjean.ch/complex-structures-and-international-organizations/ Complex Structures and International Organizations]" ({{Cite journal | issue = 2| last = Grandjean| first = Martin| title = Analisi e visualizzazioni delle reti in storia. L'esempio della cooperazione intellettuale della Società delle Nazioni | journal = Memoria e Ricerca | date = 2017| pages = 371–393| doi = 10.14647/87204}} See also: [https://halshs.archives-ouvertes.fr/halshs-01610098v2 French version]).</ref> and defined by a very unequal distribution of certain measures (some elements being highly connected and some very few, see [[complex network]]). 
* In [[software engineering]], [[programming complexity]] is a measure of the interactions of the various elements of the software. This differs from the computational complexity described above in that it is a measure of the design of the software. [[Halstead complexity measures]], [[cyclomatic complexity]], [[time complexity]], and [[parameterized complexity]] are closely linked concepts.
* In [[model theory]], [[U-rank]] is a measure of the complexity of a complete type in the context of stable theories.
* In [[bioinformatics]], [[linguistic sequence complexity]] is a measure of the vocabulary richness of a genetic text in gene sequences
* In [[statistical learning theory]], the [[Vapnik–Chervonenkis dimension]] is a measure of the size (capacity, complexity, expressive power, richness, or flexibility) of a class of sets.
* In [[computational learning theory]], [[Rademacher complexity]] is a measure of richness of a class of sets with respect to a probability distribution.
* In [[sociology]], [[social complexity]] is a [[conceptual framework]] used in the [[analysis]] of society. 
* In [[combinatorial game theory]], measures of [[game complexity]] involve understanding game positions, possible outcomes, and computation required for various game scenarios. 

Other fields introduce less precisely defined notions of complexity:

* A [[complex adaptive system]] has some or all of the following attributes:<ref name="Neil Johnson" />
** The number of parts (and types of parts) in the system and the number of relations between the parts is non-trivial – however, there is no general rule to separate "trivial" from "non-trivial";
** The system has memory or includes [[feedback]];
** The system can adapt itself according to its history or feedback;
** The relations between the system and its environment are non-trivial or non-linear;
** The system can be influenced by, or can adapt itself to, its environment;
** The system is highly sensitive to initial conditions.
*[[Peak complexity]] is the concept that human societies address problems by adding social and economic complexity, but that process is subject to diminishing marginal returns