COMPLEXITY

'Complexity' in general usage is the opposite of simplicity. 'Complexity' in specific usage is the opposite of independence, while complication is the opposite of simplicity.

Contents

Overview

Specific forms of complexity

Study of complexity

Complexity topics

Complex behaviour

Complex mechanisms

Complex simulations

Complex systems

Complexity in data

Appliciations of complexity

See also

References

Further reading

External links

Overview

Complexity in general means:

★ The state of being complex; intricacy; entanglement.

★ That which is complex; intricacy; complication.

Specific forms of complexity

In several scientific fields, "complexity" has a specific meaning :

★ In computational complexity theory, the time complexity of a problem is 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. This allows to classify problems by complexity class (such as P, NP ... ) such analysis also exists for space, that is, the memory used by the algorithm.

★ In algorithmic information theory, the ''Kolmogorov complexity'' (also called ''descriptive complexity'' or ''algorithmic entropy'') of a string is the length of the shortest binary program which outputs that string.

★ In information processing, complexity is a measure of the total number of properties transmitted by an object and detected by an observer. Such a collection of properties is often referred to as a state.

★ In physical systems, complexity is a measure of the probability of the state vector of the system. This is often confused with entropy, but is a distinct Mathematical analysis of the probability of the state of the system, where two distinct states are never conflated and considered equal as in statistical mechanics.

★ In mathematics, Krohn-Rhodes complexity is an important topic in the study of finite semigroups and automata.
There are different specific forms of complexity:

★ In the sense of how complicated a problem is from the perspective of the person trying to solve it, limits of complexity are measured using a term from cognitive psychology, namely the hrair limit.

★ Specified complexity is a term used in intelligent design theory, first coined by William Dembski.

★ Irreducible complexity is a term used in arguments against the generally accepted theory of biological evolution, being a concept popularized by the biochemist Michael Behe.

★ Unruly complexity denotes situations that do not have clearly defined boundaries, coherent internal dynamics, or simply mediated relations with their external context, as coined by Peter Taylor.

Study of complexity

Complexity has always been a part of our environment, and therefore many scientific fields have dealt with complex systems and phenomena. Indeed, some would say that only what is somehow complex – what displays variation without being random – is worthy of interest.
The use of the term complex is often confused with the term complicated. In today’s systems, this is the difference between a myriad of connecting “stovepipes” and effective “integrated” solutions. ^[1] 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 from different fields to study complexity in itself, whether it appears in anthills, human brains, or stock markets.

Complexity topics

Complex behaviour

The behaviour 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.
One of the main claims in Stephen Wolfram's book ''A New Kind of Science'' is that such behaviour can be generated by simple systems, such as the rule 110 cellular automaton.

Complex mechanisms

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

Complex 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.

Complex systems

Main articles: Complex system

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 can be biological, economic, technological, etc. Recently, complexity is a natural domain of interest of the real world socio-cognitive systems and emerging systemics research. Complex systems tend to be high-dimensional, non-linear and hard to model. In specific circumstances they may exhibit low dimensional behaviour.

Complexity in 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-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 random noise. However, those studying complex systems would not consider randomness as complexity.
Information entropy is also sometimes used in information theory as indicative of complexity.

Appliciations of complexity

Computational complexity theory is the study of the complexity of problems - that is, the difficulty of 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 in time $O(c^n)$ (where ''n'' is the size of the network to visit - let's say the number of cities the travelling salesman must visit exactly once, and $c^n$ the exponent in terms of ''n''). If the network of cities grows by 1, the time needed to solve the problem - that is, construct the shortest route that visits every city exactly once - is multiplied by a factor of c, hence the time needed to find the route grows 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 intractable.
There is another form of complexity called hierarchical complexity. It is orthogonal to the forms of complexity discussed so far, which are called horizontal complexity

See also

★ Chaos theory

★ Complexity theory (disambiguation page)

★ Command and Control Research Program

★ Evolution of complexity

★ Game complexity

★ Holism in science

★ Interconnectedness

★ Model of hierarchical complexity

★ Occam's razor

★ Programming Complexity

References

1. (Lissack and Roos, 2000)

Further reading

★ Roger Lewin. ''Complexity: Life at the Edge of Chaos''. Macmillan, 1992.

★ M. Mitchell Waldrop, ''Complexity: The Emerging Science at the Edge of Order and Chaos.'' Simon and Schuster, 1992.

★ R. V. Solé and B. C. Goodwin, ''Signs of Life: How Complexity Pervades Biology'', Basic Books, 2001.

★ Micahel R. Lissack and Johan Roos. ''The Next Common Sense, The e-Manager’s Guide to Mastering Complexity.'' Nicholas Brealey Publishing.

★ Complexity Theory and Network Centric Warfare by James Moffat (CCRP, 2003)

★ Complexity, Networking, and Effects Based Approaches to Operations by Edward Smith (CCRP, 2006)

★ Complexity, Global Politics, and National Security by Alberts and Czerwinski (CCRP, 1997)

★ Coping with the Bounds by Czerwinski (CCRP, 1998)

External links

★ Quantifying Complexity Theory - classification of complex systems

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

★ UC Four Campus Complexity Videoconferences - Human Sciences and Complexity