Complexity

The concept of complexity seems to be simple and elusive at the same time. Everyone understands what we mean when we call an object “complex,” but if we define this attribute clearly and distinctly, we encounter many difficulties.

The first difficulty arises when we want to specify to what aspect of an object we refer by calling it “complex.” Does this mean that an object has a rich structure that cannot be described easily? Or that it fulfils a difficult function? Or that it is intricate to generate this object?

Those three aspects of an object—its structure, its function, and its generative history—do not have to be equivalent in respect to complexity. Let us show this by some examples.

• A part of most intelligence tests are sequences of numbers that appear to be irregular (i.e., to have a complex structure). The task of the test person is to find out the rather simple mathematical formula that produced the sequence in question. Here, we have a complex structure but a simple generative process. In addition, this generative process is performed to fulfill a complex function, namely, to contribute to the quantification of intelligence, which is a much-debated psychological concept.
• A geometrically simple artifact like a parabolic mirror for an optical telescope is intricate to make; for example, it needs different time-consuming steps to polish it. Here, we have a simple structure but a complex generative process. Moreover, the function of such a mirror is, from a physical point of view, rather simple:It has just to focus the incoming rays of light.
• Locks have also a simple function, namely, to hinder burglars from breaking into a house. But in order to fulfill their function, they must show a complex inner structure so that it is not too easy to pick the lock.
• Mathematical set theory has a rather simple structure, which can be defined by a few axioms, but it is used to fulfill complex functions, for example, to talk in a clear way about very abstract philosophical problems, such as: Do there exist different kinds of infinity?

We can remark on a common feature of all these examples: The more space and time we need (or seem to need) for describing the structure, the function, or the generative history of an object, the more complex this object is in respect to its structure, its function, or its generative history.

[Page 540]The next difficulty consists in finding a good quantitative characterization of the relation between, on one hand, the time and space needed for describing an object and, on the other hand, the degree of complexity we ascribe to it. Such a correlation must be as abstract as necessary in order to be principally applicable to any kind of object, but it must also be as concrete as possible in order to be practically applicable to specific objects, their structure, their function, and their generative history.

The best available proposal for an abstract conceptual framework into which all those aspects can be integrated so that the complexity of a specific object can be concretely measured is based upon the idea of computation. By “computation,” we understand an ordered sequence of mathematically describable operations that is effective for solving a problem and that can be executed by a computer if it is formulated as an algorithm in a programming language. To sum up two ratios is as well a computation in that sense as the meteorological modeling of tomorrow's weather.

...