Complexity (other)
   HOME

TheInfoList



OR:

Complexity characterises the behaviour of a system or
model A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure. Models c ...
whose components interact in multiple ways and follow local rules, leading to
non-linearity In mathematics and science, a nonlinear system is a system in which the change of the output is not proportional to the change of the input. Nonlinear problems are of interest to engineers, biologists, physicists, mathematicians, and many othe ...
,
randomness In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual rand ...
, collective dynamics, hierarchy, and emergence. The term is generally used to characterize something with many parts where those parts interact with each other in multiple ways, culminating in a higher order of emergence greater than the sum of its parts. The study of these complex linkages at various scales is the main goal of
complex systems theory A complex system is a system composed of many components which may interact with each other. Examples of complex systems are Earth's global climate, organisms, the human brain, infrastructure such as power grid, transportation or communication sy ...
. The intuitive criterion of complexity can be formulated as follows: a system would be more complex if more parts could be distinguished, and if more connections between them existed. , a number of approaches to characterizing complexity have been used in
science Science is a systematic endeavor that Scientific method, builds and organizes knowledge in the form of Testability, testable explanations and predictions about the universe. Science may be as old as the human species, and some of the earli ...
; Zayed ''et al.'' reflect many of these. Neil Johnson states that "even among scientists, there is no unique definition of complexity – and the scientific notion has traditionally been conveyed using particular examples..." Ultimately Johnson adopts the definition of "complexity science" as "the study of the phenomena which emerge from a collection of interacting objects".


Overview

Definitions of complexity often depend on the concept of a " system" – a set of parts or elements that have relationships among them differentiated from relationships with other elements outside the relational regime. Many definitions tend to postulate or assume that complexity expresses a condition of numerous elements in a system and numerous forms of relationships among the elements. However, what one sees as complex and what one sees as simple is relative and changes with time.
Warren Weaver Warren Weaver (July 17, 1894 – November 24, 1978) was an American scientist, mathematician, and science administrator. He is widely recognized as one of the pioneers of machine translation and as an important figure in creating support for scien ...
posited in 1948 two forms of complexity: disorganized complexity, and organized complexity. Phenomena of 'disorganized complexity' are treated using
probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set ...
and statistical mechanics, while 'organized complexity' deals with phenomena that escape such approaches and confront "dealing simultaneously with a sizable number of factors which are interrelated into an organic whole". Weaver's 1948 paper has influenced subsequent thinking about complexity. The approaches that embody concepts of systems, multiple elements, multiple relational regimes, and state spaces might be summarized as implying that complexity arises from the number of distinguishable relational regimes (and their associated state spaces) in a defined system. Some definitions relate to the algorithmic basis for the expression of a complex phenomenon or model or mathematical expression, as later set out herein.


Disorganized vs. organized

One of the problems in addressing complexity issues has been formalizing the intuitive conceptual distinction between the large number of variances in relationships extant in random collections, and the sometimes large, but smaller, number of relationships between elements in systems where constraints (related to correlation of otherwise independent elements) simultaneously reduce the variations from element independence and create distinguishable regimes of more-uniform, or correlated, relationships, or interactions. Weaver perceived and addressed this problem, in at least a preliminary way, in drawing a distinction between "disorganized complexity" and "organized complexity". In Weaver's view, disorganized complexity results from the particular system having a very large number of parts, say millions of parts, or many more. Though the interactions of the parts in a "disorganized complexity" situation can be seen as largely random, the properties of the system as a whole can be understood by using probability and statistical methods. A prime example of disorganized complexity is a gas in a container, with the gas molecules as the parts. Some would suggest that a system of disorganized complexity may be compared with the (relative)
simplicity Simplicity is the state or quality of being simple. Something easy to understand or explain seems simple, in contrast to something complicated. Alternatively, as Herbert A. Simon suggests, something is simple or complex depending on the way we ...
of planetary orbits – the latter can be predicted by applying
Newton's laws of motion Newton's laws of motion are three basic laws of classical mechanics that describe the relationship between the motion of an object and the forces acting on it. These laws can be paraphrased as follows: # A body remains at rest, or in moti ...
. Of course, most real-world systems, including planetary orbits, eventually become theoretically unpredictable even using Newtonian dynamics; as discovered by modern chaos theory. Organized complexity, in Weaver's view, resides in nothing else than the non-random, or correlated, interaction between the parts. These correlated relationships create a differentiated structure that can, as a system, interact with other systems. The coordinated system manifests properties not carried or dictated by individual parts. The organized aspect of this form of complexity in regards to other systems, rather than the subject system, can be said to "emerge," without any "guiding hand". The number of parts does not have to be very large for a particular system to have emergent properties. A system of organized complexity may be understood in its properties (behavior among the properties) through
modeling A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure. Models c ...
and
simulation A simulation is the imitation of the operation of a real-world process or system over time. Simulations require the use of models; the model represents the key characteristics or behaviors of the selected system or process, whereas the s ...
, particularly modeling and simulation with computers. An example of organized complexity is a city neighborhood as a living mechanism, with the neighborhood people among the system's parts.


Sources and factors

There are generally rules which can be invoked to explain the origin of complexity in a given system. The source of disorganized complexity is the large number of parts in the system of interest, and the lack of correlation between elements in the system. In the case of
self-organizing Self-organization, also called spontaneous order in the social sciences, is a process where some form of overall order and disorder, order arises from local interactions between parts of an initially disordered system. The process can be spon ...
living systems Living systems are open self-organizing life forms that interact with their environment. These systems are maintained by flows of information, energy and matter. In the last few decades, some scientists have proposed that a general living syst ...
, usefully organized complexity comes from beneficially mutated organisms being selected to survive by their environment for their differential reproductive ability or at least success over inanimate
matter In classical physics and general chemistry, matter is any substance that has mass and takes up space by having volume. All everyday objects that can be touched are ultimately composed of atoms, which are made up of interacting subatomic part ...
or less organized complex organisms. See e.g.
Robert Ulanowicz Robert Edward Ulanowicz ( ) is an American theoretical ecologist and philosopher of Polish descent who in his search for a ''unified theory of ecology'' has formulated a paradigm he calls ''Process Ecology''. He was born September 17, 1943 in B ...
's treatment of
ecosystems An ecosystem (or ecological system) consists of all the organisms and the physical environment with which they interact. These biotic and abiotic components are linked together through nutrient cycles and energy flows. Energy enters the syst ...
. Complexity of an object or system is a relative property. For instance, for many functions (problems), such a computational complexity as time of computation is smaller when multitape
Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
s are used than when Turing machines with one tape are used. Random Access Machines allow one to even more decrease time complexity (Greenlaw and Hoover 1998: 226), while inductive Turing machines can decrease even the complexity class of a function, language or set (Burgin 2005). This shows that tools of activity can be an important factor of complexity.


Varied meanings

In several scientific fields, "complexity" has a precise meaning: * In
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, the amounts of resources required for the execution of
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
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 size of the input (usually measured in bits), using the most efficient
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
, and the space complexity of a problem equal to the volume of the
memory Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered ...
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 In computational complexity theory, a complexity class is a set (mathematics), set of computational problems of related resource-based computational complexity, complexity. The two most commonly analyzed resources are time complexity, time and spa ...
(such as P, NP, etc.). An
axiomatic An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or ...
approach to computational complexity was developed by
Manuel Blum Manuel Blum (born 26 April 1938) is a Venezuelan-American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and ...
. 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 Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as str ...
, the ''
Kolmogorov complexity In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produ ...
'' (also called ''descriptive complexity'', ''algorithmic complexity'' or ''algorithmic
entropy Entropy is a scientific concept, as well as a measurable physical property, that is most commonly associated with a state of disorder, randomness, or uncertainty. The term and the concept are used in diverse fields, from classical thermodynam ...
'') of a string is the length of the shortest binary
program Program, programme, programmer, or programming may refer to: Business and management * Program management, the process of managing several related projects * Time management * Program, a part of planning Arts and entertainment Audio * Progra ...
that outputs that string.
Minimum message length Minimum message length (MML) is a Bayesian information-theoretic method for statistical model comparison and selection. It provides a formal information theory restatement of Occam's Razor: even when models are equal in their measure of fit-accurac ...
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 In computational complexity theory the Blum axioms or Blum complexity axioms are axioms that specify desirable properties of complexity measures on the set of computable functions. The axioms were first defined by Manuel Blum in 1967. Importantly ...
(Blum 1967) was introduced by Mark Burgin in the paper presented for publication by
Andrey Kolmogorov Andrey Nikolaevich Kolmogorov ( rus, Андре́й Никола́евич Колмого́ров, p=ɐnˈdrʲej nʲɪkɐˈlajɪvʲɪtɕ kəlmɐˈɡorəf, a=Ru-Andrey Nikolaevich Kolmogorov.ogg, 25 April 1903 – 20 October 1987) was a Sovi ...
. 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
theorems In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of the ...
, 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). 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, 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. * In mathematics, Krohn–Rhodes complexity is an important topic in the study of finite semigroups and automata theory, automata. * In Network theory complexity is the product of richness in the connections between components of a system, 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. Other fields introduce less precisely defined notions of complexity: * A complex adaptive system has some or all of the following attributes: ** 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.


Study

Complexity has always been a part of our environment, and therefore many scientific fields have dealt with Complex system, complex systems and phenomena. From one perspective, that which is somehow complex – displaying variation without being random – is most worthy of interest given the rewards found in the depths of exploration. The use of the term complex is often confused with the term complicated. In today's systems, this is the difference between myriad connecting "stovepipes" and effective "integrated" solutions. This means that complex is the opposite of independent, while complicated is the opposite of simple. While this has led some fields to come up with specific definitions of complexity, there is a more recent movement to regroup observations interdisciplinarity, from different fields to study complexity in itself, whether it appears in anthills, human brains or Social system, social systems. One such interdisciplinary group of fields is relational order theories.


Topics


Behaviour

The behavior of a complex system is often said to be due to emergence and self-organization. Chaos theory has investigated the sensitivity of systems to variations in initial conditions as one cause of complex behaviour.


Mechanisms

Recent developments in artificial life, evolutionary computation and genetic algorithms have led to an increasing emphasis on complexity and complex adaptive systems.


Simulations

In social science, the study on the emergence of macro-properties from the micro-properties, also known as macro-micro view in sociology. The topic is commonly recognized as social complexity that is often related to the use of computer simulation in social science, i.e. computational sociology.


Systems

Systems theory has long been concerned with the study of complex systems (in recent times, ''complexity theory'' and ''complex systems'' have also been used as names of the field). These systems are present in the research of a variety disciplines, including biology, economics, social studies and technology. Recently, complexity has become a natural domain of interest of real world socio-cognitive systems and emerging systemics research. Complex systems tend to be high-dimensional, non-linear, and difficult to model. In specific circumstances, they may exhibit low-dimensional behaviour.


Data

In information theory, algorithmic information theory is concerned with the complexity of strings of data. Complex strings are harder to compress. While intuition tells us that this may depend on the codec used to compress a string (a codec could be theoretically created in any arbitrary language, including one in which the very small command "X" could cause the computer to output a very complicated string like "18995316"), any two Turing completeness, Turing-complete languages can be implemented in each other, meaning that the length of two encodings in different languages will vary by at most the length of the "translation" language – which will end up being negligible for sufficiently large data strings. These algorithmic measures of complexity tend to assign high values to signal noise, random noise. However, under a certain understanding of complexity, arguably the most intuitive one, random noise is meaningless and so not complex at all. Information entropy is also sometimes used in information theory as indicative of complexity, but entropy is also high for randomness. In the case of complex systems, information fluctuation complexity was designed so as not to measure randomness as complex and has been useful in many applications. More recently, a complexity metric was developed for images that can avoid measuring noise as complex by using the minimum description length principle.


Classification Problems

There has also been interest in measuring the complexity of classification problems in Supervised learning, supervised machine learning. This can be useful in meta-learning (computer science), meta-learning to determine for which data sets filtering (or removing suspected noisy instances from the training set) is the most beneficial and could be expanded to other areas. For binary classification, such measures can consider the overlaps in feature values from differing classes, the separability of the classes, and measures of geometry, topology, and density of manifolds. For non-binary classification problems, instance hardness is a bottom-up approach that first seeks to identify instances that are likely to be misclassified (assumed to be the most complex). The characteristics of such instances are then measured using supervised learning, supervised measures such as the number of disagreeing neighbors or the likelihood of the assigned class label given the input features.


In molecular recognition

A recent study based on Molecular modelling, molecular simulations and compliance constants describes molecular recognition as a phenomenon of organisation. Even for small molecules like carbohydrates, the recognition process can not be predicted or designed even assuming that each individual hydrogen bond's strength is exactly known.


The law of requisite complexity

Driving from the Variety (cybernetics)#Law of requisite variety, law of requisite variety, Boisot and McKelvey formulated the ‘Law of Requisite Complexity’, that holds that, in order to be efficaciously adaptive, the internal complexity of a system must match the external complexity it confronts.


Positive, appropriate and negative complexity

The application in project management of the Law of Requisite Complexity, as proposed by Stefan Morcov, is the analysis of Project complexity#Positive, appropriate (requisite), and negative complexity, positive, appropriate and negative complexity.Morcov, S. (2021). Managing Positive and Negative Complexity: Design and Validation of an IT Project Complexity Management Framework. KU Leuven University. Available at https://lirias.kuleuven.be/retrieve/637007


In project management

Project complexity is the property of a project which makes it difficult to understand, foresee, and keep under control its overall behavior, even when given reasonably complete information about the project system.


In systems engineering

Maik Maurer considers complexity as a reality in engineering. He proposed a methodology for managing complexity in systems engineering :                              1.           Define the system.                              2.           Identify the type of complexity.                              3.           Determine the strategy.                              4.           Determine the method.                              5.           Model the system.                              6.           Implement the method.


Applications

Computational complexity theory is the study of the complexity of problems – that is, the difficulty of problem solving, solving them. Problems can be classified by complexity class according to the time it takes for an algorithm – usually a computer program – to solve them as a function of the problem size. Some problems are difficult to solve, while others are easy. For example, some difficult problems need algorithms that take an exponential amount of time in terms of the size of the problem to solve. Take the travelling salesman problem, for example. It can be solved, as denoted in Big O notation, in time O(n^2 2^n) (where ''n'' is the size of the network to visit – the number of cities the travelling salesman must visit exactly once). As the size of the network of cities grows, the time needed to find the route grows (more than) exponentially. Even though a problem may be computationally solvable in principle, in actual practice it may not be that simple. These problems might require large amounts of time or an inordinate amount of space. Computational complexity may be approached from many different aspects. Computational complexity can be investigated on the basis of time, memory or other resources used to solve the problem. Time and space are two of the most important and popular considerations when problems of complexity are analyzed. There exist a certain class of problems that although they are solvable in principle they require so much time or space that it is not practical to attempt to solve them. These problems are called Computational complexity theory#Intractability, intractable. There is another form of complexity called Model of hierarchical complexity, hierarchical complexity. It is orthogonal to the forms of complexity discussed so far, which are called horizontal complexity.


Emerging applications in other fields

The concept of complexity is being increasingly used in the study of cosmology, Big History, big history, and Cultural Evolution, cultural evolution with increasing granularity, as well as increasing quantification.


Application in cosmology

Eric Chaisson has advanced a cosmoglogical complexity metric which he terms Energy Rate Density. This approach has been expanded in various works, most recently applied to measuring evolving complexity of nation-states and their growing cities.Chaisson, Eric J. "Energy Budgets of Evolving Nations and Their Growing Cities", Energies 15, no. 21 (2022): 8212.


See also

* Assembly theory * Chaos theory * Complexity theory (disambiguation), Complexity theory (disambiguation page) *Complex network *Complex system * Cyclomatic complexity * Digital morphogenesis * Dual-phase evolution * Emergence * Evolution of complexity *Fractal * Game complexity * Holism in science * Law of Complexity/Consciousness * Model of hierarchical complexity * Names of large numbers * Network science * Network theory * Novelty theory * Occam's razor *Percolation theory * Process architecture * Programming Complexity * Sociology and complexity science * Systems theory * Thorngate's postulate of commensurate complexity * Variety (cybernetics) * Volatility, uncertainty, complexity and ambiguity * Arthur Winfree * Computational irreducibility * Zero-Force Evolutionary Law * Project management#Project complexity, Project complexity


References


Further reading

* * * * * * 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 * Meyers, R.A., (2009) "Encyclopedia of Complexity and Systems Science", * Mitchell, M. (2009). Complexity: A Guided Tour. Oxford University Press, Oxford, UK. * Gershenson, C., Ed. (2008). Complexity: 5 Questions. Automatic Peess / VIP.


External links


Complexity Measures
– an article about the abundance of not-that-useful complexity measures.

– Introductory complex system course by Melanie Mitchell
Santa Fe Institute
focusing on the study of complexity science
Lecture Videos


– Human Sciences and Complexity {{Authority control Abstraction Chaos theory Complex systems theory Holism Systems Transdisciplinarity