Home      Discussion      Topics      Dictionary      Almanac
Signup       Login
Complexity

Complexity

Overview
In general usage, complexity tends to be used to characterize something with many parts in intricate arrangement. The study of these complex linkages is the main goal of complex systems theory. In science
Science
Science is a systematic enterprise that builds and organizes knowledge in the form of testable explanations and predictions about the universe...

 there are at this time a number of approaches to characterizing complexity, many of which are reflected in this article. In a business context, complexity management
Complexity management
Complexity management is a business methodology that deals with the analysis and optimization of complexity in enterprises. Effects of complexity pertain to all business processes along the value chain and hence complexity management requires a holistic approach...

 is the methodology to minimize value-destroying complexity and efficiently control value-adding complexity in a cross-functional approach.


Definitions are often tied to the concept of a "system
System
System is a set of interacting or interdependent components forming an integrated whole....

"—a set of parts or elements that have relationships among them differentiated from relationships with other elements outside the relational regime.
Discussion
Ask a question about 'Complexity'
Start a new discussion about 'Complexity'
Answer questions from other users
Full Discussion Forum
 
Recent Discussions
Encyclopedia
In general usage, complexity tends to be used to characterize something with many parts in intricate arrangement. The study of these complex linkages is the main goal of complex systems theory. In science
Science
Science is a systematic enterprise that builds and organizes knowledge in the form of testable explanations and predictions about the universe...

 there are at this time a number of approaches to characterizing complexity, many of which are reflected in this article. In a business context, complexity management
Complexity management
Complexity management is a business methodology that deals with the analysis and optimization of complexity in enterprises. Effects of complexity pertain to all business processes along the value chain and hence complexity management requires a holistic approach...

 is the methodology to minimize value-destroying complexity and efficiently control value-adding complexity in a cross-functional approach.

Overview


Definitions are often tied to the concept of a "system
System
System is a set of interacting or interdependent components forming an integrated whole....

"—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. At the same time, what is complex and what is simple is relative and changes with time.

Some definitions key on the question of the probability of encountering a given condition of a system once characteristics of the system are specified. Warren Weaver
Warren Weaver
Warren Weaver was an American scientist, mathematician, and science administrator...

 has posited that the complexity of a particular system
System
System is a set of interacting or interdependent components forming an integrated whole....

 is the degree of difficulty in predicting the properties of the system, if the properties of the system's parts are given. (unsubstatiated citation: please read the discussions page) . In Weaver's view, complexity comes in two forms: disorganized complexity, and organized complexity.
Weaver's
Warren Weaver
Warren Weaver was an American scientist, mathematician, and science administrator...

 paper has influenced contemporary 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 is later set out herein.

Disorganized complexity vs. organized complexity


One of the problems in addressing complexity issues has been distinguishing conceptually 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, for example, with the (relative) simplicity
Simplicity
Simplicity is the state or quality of being simple. It usually relates to the burden which a thing puts on someone trying to explain or understand it. Something which is easy to understand or explain is simple, in contrast to something complicated...

 of the planetary orbits—the latter can be known by applying Newton's laws of motion
Newton's laws of motion
Newton's laws of motion are three physical laws that form the basis for classical mechanics. They describe the relationship between the forces acting on a body and its motion due to those forces...

, though this example involved highly correlated events.

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 vis a vis to other systems than the subject system can be said to "emerge,"
Emergence
In philosophy, systems theory, science, and art, emergence is the way complex systems and patterns arise out of a multiplicity of relatively simple interactions. Emergence is central to the theories of integrative levels and of complex systems....

 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 and simulation
Simulation
Simulation is the imitation of some real thing available, state of affairs, or process. The act of simulating something generally entails representing certain key characteristics or behaviours of a selected physical or abstract system....

, particularly modeling and simulation with computers
Computer simulation
A computer simulation, a computer model, or a computational model is a computer program, or network of computers, that attempts to simulate an abstract model of a particular system...

. 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 of complexity


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.

There is no consensus at present on general rules regarding the sources of organized complexity, though the lack of randomness implies correlations between elements. See e.g. Robert Ulanowicz
Robert Ulanowicz
Robert Edward Ulanowicz is an American theoretical ecologist and philosopher who is best known for his search for a unified theory of ecology. He was born September 17, 1943 in Baltimore, Maryland....

's treatment of ecosystems. Consistent with prior statements here, the number of parts (and types of parts) in the system and the number of relations between the parts would have to be non-trivial—however, there is no general rule to separate "trivial" from "non-trivial".

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
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...

s are used than when Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...

s with one tape are used. Random Access Machine
Random access machine
In computer science, random access machine is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers...

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

Specific meanings of complexity


In several scientific fields, "complexity" has a specific meaning:
  • In computational complexity theory
    Computational complexity theory
    Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

    , the amounts of resources
    Computational resource
    In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems....

     required for the execution of algorithm
    Algorithm
    In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

    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
    Algorithm
    In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

    , and the space complexity of a problem equal to the volume of the memory
    Computer storage
    Computer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....

     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
    Algorithm
    In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

    . This allows to classify computational problems by complexity class
    Complexity class
    In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...

     (such as P
    P (complexity)
    In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...

    , NP
    NP (complexity)
    In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...

     ... ). An axiomatic approach to computational complexity
    Computational complexity theory
    Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

     was developed by Manuel Blum
    Manuel Blum
    Manuel Blum is a 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 program checking".-Biography:Blum attended MIT, where he received his bachelor's degree 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
    Algorithmic information theory is a subfield of information theory and computer science that concerns itself with the relationship between computation and information...

    , the Kolmogorov complexity
    Kolmogorov complexity
    In algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...

    (also called descriptive complexity, algorithmic complexity or algorithmic entropy) of a string
    String (computer science)
    In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....

     is the length of the shortest binary program
    Computer program
    A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...

     that outputs that string. 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
    Kolmogorov complexity
    In algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...

     based on Blum axioms
    Blum axioms
    In computational complexity theory the Blum axioms or Blum complexity axioms are axioms which specify desirable properties of complexity measures on the set of computable functions. The axioms were first defined by Manuel Blum in 1967....

     (Blum 1967) was introduced by Mark Burgin in the paper presented for publication by Andrey Kolmogorov
    Andrey Kolmogorov
    Andrey Nikolaevich Kolmogorov was a Soviet mathematician, preeminent in the 20th century, who advanced various scientific fields, among them probability theory, topology, intuitionistic logic, turbulence, classical mechanics and computational complexity.-Early life:Kolmogorov was born at Tambov...

     (Burgin 1982). The axiomatic approach encompasses other approaches to Kolmogorov complexity
    Kolmogorov complexity
    In algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...

    . It is possible to treat different kinds of Kolmogorov complexity
    Kolmogorov complexity
    In algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...

     as particular cases of axiomatically defined generalized Kolmogorov complexity
    Kolmogorov complexity
    In algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...

    . Instead, of proving similar 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 processing
    Information processing
    Information processing is the change of information in any manner detectable by an observer. As such, it is a process which describes everything which happens in the universe, from the falling of a rock to the printing of a text file from a digital computer system...

    , complexity is a measure of the total number of properties
    Property
    Property is any physical or intangible entity that is owned by a person or jointly by a group of people or a legal entity like a corporation...

     transmitted by an object and detected by an observer
    Observation
    Observation is either an activity of a living being, such as a human, consisting of receiving knowledge of the outside world through the senses, or the recording of data using scientific instruments. The term may also refer to any data collected during this activity...

    . Such a collection of properties is often referred to as a state
    State (computer science)
    In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....

    .

  • In business, complexity describes the variances and their consequences in various fields such as product portfolio, technologies, markets and market segments, locations, manufacturing network, customer portfolio, IT systems, organization, processes etc.

  • In physical systems, complexity is a measure of the probability
    Probability
    Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...

     of the state vector
    State vector
    *A state vector in general control systems describes the observed states of an object in state space, e.g. in variables of the degrees of freedom for motion *A state vector in general control systems describes the observed states of an object in state space, e.g. in variables of the degrees of...

     of the system
    System
    System is a set of interacting or interdependent components forming an integrated whole....

    . This should not be confused with entropy
    Entropy (disambiguation)
    Entropy, in thermodynamics, is a measure of the energy in a thermodynamic system not available to do useful work.Entropy may also refer to:-Thermodynamics:*Entropy , the macroscopic approach to thermodynamic 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 statistical mechanics
    Statistical mechanics
    Statistical mechanics or statistical thermodynamicsThe terms statistical mechanics and statistical thermodynamics are used interchangeably...

    .

  • In mathematics
    Mathematics
    Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

    , Krohn-Rhodes complexity is an important topic in the study of finite semigroup
    Semigroup
    In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...

    s and automata
    Automata theory
    In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...

    .

  • In software engineering
    Software engineering
    Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...

    , programming complexity
    Programming Complexity
    Programming complexity is a term that encompasses numerous properties of a piece of software, all of which affect internal interactions. According to several commentators, there is a distinction between the terms complex and complicated. Complicated implies being difficult to understand but with...

     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.


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
    Cognitive psychology
    Cognitive psychology is a subdiscipline of psychology exploring internal mental processes.It is the study of how people perceive, remember, think, speak, and solve problems.Cognitive psychology differs from previous psychological approaches in two key ways....

    , namely the hrair limit.

  • Complex adaptive system
    Complex adaptive system
    Complex adaptive systems are special cases of complex systems. They are complex in that they are dynamic networks of interactions and relationships not aggregations of static entities...

     denotes systems that have 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
      Feedback
      Feedback describes the situation when output from an event or phenomenon in the past will influence an occurrence or occurrences of the same Feedback describes the situation when output from (or information about the result of) an event or phenomenon in the past will influence an occurrence or...

      ;
    • 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; and
    • The system is highly sensitive to initial conditions.

Study of complexity


Complexity has always been a part of our environment, and therefore many scientific
Science
Science is a systematic enterprise that builds and organizes knowledge in the form of testable explanations and predictions about the universe...

 fields have dealt with complex systems and phenomena. From one perspective, that which is somehow complex-—displaying variation without being random
Randomness
Randomness has somewhat differing meanings as used in various fields. It also has common meanings which are connected to the notion of predictability of events....

—-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 from different fields
Interdisciplinarity
Interdisciplinarity involves the combining of two or more academic fields into one single discipline. An interdisciplinary field crosses traditional boundaries between academic disciplines or schools of thought, as new needs and professions have emerged....

 to study complexity in itself, whether it appears in anthills, human brain
Human brain
The human brain has the same general structure as the brains of other mammals, but is over three times larger than the brain of a typical mammal with an equivalent body size. Estimates for the number of neurons in the human brain range from 80 to 120 billion...

s, or stock market
Stock market
A stock market or equity market is a public entity for the trading of company stock and derivatives at an agreed price; these are securities listed on a stock exchange as well as those only traded privately.The size of the world stock market was estimated at about $36.6 trillion...

s. One such interdisciplinary group of fields is relational order theories
Relational order theories
A number of independent lines of research depict the universe, including the social organization of living creatures which is of particular interest to humans, as systems, or networks, of relationships....

.

Complex behaviour


The behavior of a complex system is often said to be due to emergence
Emergence
In philosophy, systems theory, science, and art, emergence is the way complex systems and patterns arise out of a multiplicity of relatively simple interactions. Emergence is central to the theories of integrative levels and of complex systems....

 and self-organization
Self-organization
Self-organization is the process where a structure or pattern appears in a system without a central authority or external element imposing it through planning...

. Chaos theory
Chaos theory
Chaos theory is a field of study in mathematics, with applications in several disciplines including physics, economics, biology, and philosophy. Chaos theory studies the behavior of dynamical systems that are highly sensitive to initial conditions, an effect which is popularly referred to as the...

 has investigated the sensitivity of systems to variations in initial conditions as one cause of complex behaviour.

Complex mechanisms


Recent developments around artificial life
Artificial life
Artificial life is a field of study and an associated art form which examine systems related to life, its processes, and its evolution through simulations using computer models, robotics, and biochemistry. The discipline was named by Christopher Langton, an American computer scientist, in 1986...

, evolutionary computation
Evolutionary computation
In computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....

 and genetic algorithm
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...

s 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
Sociology
Sociology is the study of society. It is a social science—a term with which it is sometimes synonymous—which uses various methods of empirical investigation and critical analysis to develop a body of knowledge about human social activity...

. The topic is commonly recognized as social complexity
Social complexity
In the discipline of sociology, social complexity is a theoretical construct useful in the analysis of society.- Overview :Contemporary definitions of complexity in the sciences are found in relation to systems theory, where a phenomenon under study has many parts and many possible arrangements of...

 that is often related to the use of computer simulation
Computer simulation
A computer simulation, a computer model, or a computational model is a computer program, or network of computers, that attempts to simulate an abstract model of a particular system...

 in social science, i.e.: computational sociology
Computational sociology
Computational sociology is a branch of sociology that uses computationally intensive methods to analyze and model social phenomena. Using computer simulations, artificial intelligence, complex statistical methods, and new analytic approaches like social network analysis, computational sociology...

.

Complex systems



Systems theory
Systems theory
Systems theory is the transdisciplinary study of systems in general, with the goal of elucidating principles that can be applied to all types of systems at all nesting levels in all fields of research...

 has long been concerned with the study of complex system
Complex system
A complex system is a system composed of interconnected parts that as a whole exhibit one or more properties not obvious from the properties of the individual parts....

s (In recent times, complexity theory and complex systems have also been used as names of the field). These system
System
System is a set of interacting or interdependent components forming an integrated whole....

s can be biological
Biology
Biology is a natural science concerned with the study of life and living organisms, including their structure, function, growth, origin, evolution, distribution, and taxonomy. Biology is a vast subject containing many subdivisions, topics, and disciplines...

, economic, technological
Technology
Technology is the making, usage, and knowledge of tools, machines, techniques, crafts, systems or methods of organization in order to solve a problem or perform a specific function. It can also refer to the collection of such tools, machinery, and procedures. The word technology comes ;...

, etc. Recently, complexity is a natural domain of interest of the real world socio-cognitive systems and emerging systemics
Systemics
In the context of systems science and systems philosophy, the term systemics refers to an initiative to study systems from a holistic point of view...

 research. Complex systems tend to be high-dimension
Dimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...

al, non-linear and hard to model. In specific circumstances they may exhibit low dimensional behaviour.

Complexity in data


In information theory
Information theory
Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...

, algorithmic information theory
Algorithmic information theory
Algorithmic information theory is a subfield of information theory and computer science that concerns itself with the relationship between computation and information...

 is concerned with the complexity of strings
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....

 of data.

Complex strings are harder to compress. While intuition tells us that this may depend on the codec
Codec
A codec is a device or computer program capable of encoding or decoding a digital data stream or signal. The word codec is a portmanteau of "compressor-decompressor" or, more commonly, "coder-decoder"...

 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
Turing completeness
In computability theory, a system of data-manipulation rules is said to be Turing complete or computationally universal if and only if it can be used to simulate any single-taped Turing machine and thus in principle any computer. A classic example is the lambda calculus...

 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
Randomness
Randomness has somewhat differing meanings as used in various fields. It also has common meanings which are connected to the notion of predictability of events....

 as complexity.

Information entropy
Information entropy
In information theory, entropy is a measure of the uncertainty associated with a random variable. In this context, the term usually refers to the Shannon entropy, which quantifies the expected value of the information contained in a message, usually in units such as bits...

 is also sometimes used in information theory as indicative of complexity.

Applications of complexity


Computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

 is the study of the complexity of problems—that is, the difficulty of solving
Problem solving
Problem solving is a mental process and is part of the larger problem process that includes problem finding and problem shaping. Consideredthe most complex of all intellectual functions, problem solving has been defined as higher-order cognitive process that requires the modulation and control of...

 them. Problems can be classified by complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...

 according to the time it takes for an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

—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
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...

, for example. It can be solved in time (where n is the size of the network to visit—let's say 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
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...

 may be approached from many different aspects. Computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*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
Model of hierarchical complexity
The model of hierarchical complexity is a framework for scoring how complex a behavior is. It quantifies the order of hierarchical complexity of a task based on mathematical principles of how the information is organized and of information science...

. It is orthogonal to the forms of complexity discussed so far, which are called horizontal complexity

Bejan and Lorente showed that complexity is modest (not maximum, not increasing), and is a feature of the natural phenomenon of design generation in nature, which is predicted by the Constructal law.

Bejan and Lorente also showed that all the optimality (max,min) statements have limited ad-hoc applicability, and are unified under the Constructal law of design and evolution in nature.

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", ISBN 978-0-387-75888-6

External links