Complexity - Varied Meanings of Complexity

Varied Meanings of Complexity

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

• In computational complexity theory, the amounts of resources required for the execution of algorithms 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, and the space complexity of a problem equal to the volume of the 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 to classify computational problems by complexity class (such as P, NP ... ). An 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) of a string is the length of the shortest binary program 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 based on Blum axioms (Blum 1967) was introduced by Mark Burgin in the paper presented for publication by Andrey Kolmogorov (Burgin 1982). 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, 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, 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 should not be confused with 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 mathematics, Krohn–Rhodes complexity is an important topic in the study of finite semigroups and automata.

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

• The hrair limit is a concept from cognitive psychology that considers how complicated a problem is from the perspective of the person trying to solve it. It denotes the limits of manageable complexity. This concept was used by Ed Yourdon in his Modern Structured Analysis (Prentice Hall, 1979) to mean the maximum number of subroutines that should be called from the main program (in order to avoid confusing the programmer).

• In business, the term 'complexity' is used with varied meanings to denote difficult management challenges in product portfolio, technologies, markets and market segments, locations, manufacturing network, customer portfolio, IT systems, organization, processes etc.

• Advocates of intelligent design introduce the phrase irreducible complexity to denote a degree of systemic interdependence that is too great to be achieved without divine intervention.