4.2 Complexity: Structural, Behavioral, and Computational


4.2 Complexity: Structural, Behavioral, and Computational

The world around us is complex. This is the reality that defines our knowledge of the different phenomena we face every day. Complexity shows up in absolutely diverse fields of human activity, beginning from complicated engineering designs and continuing up to sophisticated economic and social problems.

Stafford Beer, former President of the U.S.A. General System Research Society, considered complexity as an integral property of the real world (Beer 1970). He declared that understanding complexity has become the problem of the century—just as the skill to process metals was essential for our ancestors.

According to Casti (1979), the concept of complexity embraces three basic aspects (italics added): "Static complexity represents essentially the complexity of the subsystems that realize the system, dynamic complexity involves the computational length required by the subsystems' interconnection to realize the process, and control complexity represents a measure of computational requirements needed to keep the system behaving in a prescribed fashion" (44).

Following Casti (1979), let us consider three basic hypostases of the complexity inherent in biomolecular systems capable of information processing. Given the biological background of the problems discussed, let us use the following terms:

  • Structural complexity of the system (static)

  • Behavioral complexity that determines the spatiotemporal evolution of the system performing an information processing operation (dynamic)

  • Computational complexity of an algorithm describing information processing operations performed (control)

Several approaches to the quantitative definition of complexity are now in use. The notion of algorithmic complexity seems to be the most adequate for estimating the complexity of the evolution of a dynamic system (Yudin and Yudin 1985; Ming and Vitanyi 1993).

Suppose there is some system that transforms input information x X into output information y Y according to some program p. Here, X and Y are sets of x and y values. According to Yudin and Yudin (1985), the structure of the system is defined as a description of its operational (hardware) characteristics—that is, function φ(p|x) = y, that can be used by program p. It is essential that this description does not depend on the choice of input data.

The algorithmic complexity of the process performed by a system having the structure φ(p|x) = y (that is, its behavioral complexity) is defined as the minimal length of the assumed program l(p) from some set of programs S, that describe the process adequately:

Given the definition of the system structure, it is possible to introduce the notion of the structural complexity of the system itself as complexity Kφ(y|x) under fixed values of x = x0:

Numerical estimations of algorithmic behavioral and structural complexity are not used in this chapter. All examples discussed below are chosen such that the high (or low) degree of behavioral complexity is evident.

The behavioral complexity in a reaction-diffusion medium is considered to be high. It is determined by nonlinear dynamics inherent in the medium that lead to different spatiotemporal modes, depending on the state of the medium and control stimuli. In any case, the behavior of the medium is much more complicated than the behavior of a semiconductor electronic circuit (YES or no mode).

The computational complexity of an algorithm describing the behavior of a system can be expressed as the dependence of computational capabilities (resources) that are necessary to simulate system behavior (i.e., a specific system characteristic called the problem size).

Several types of so-called complexity functions are used for quantitative estimation of computational complexity. The most known among them are:

  • Time complexity function (Klir 1985)

    that is, the number of time steps necessary for algorithm A to solve individual problem x determined by the length of the word |x| equal to n.

  • Space complexity function (Klir 1985)

    where SA(x) is a number of memory cells necessary for algorithm A.

The algorithm for solving a problem is called polynomial (P type) if the complexity function is polynomially dependent on the problem size. Otherwise, if the complexity function is exponentially dependent on the problem size, the problem is defined as intractable. Several types of these problems having different complexity are known (NP, NP-complete, and so on).

The computational complexity of a particular problem can differ according to the type of machine used to solve it. The problem may scale differently for each type of machine. As an example, let us consider a two-dimensional contour enhancement operation performed by a digital von Neumann machine and a reaction-diffusion machine. Let us choose as the problem size the linear dimensions of an image (the number of points along each axis necessary for performing this operation without contour distortions).

For a digital computer, this operation is equivalent in the general case to a large number of primitive binary operations performed on a two-dimensional array of variables. The complexity function should be proportional to the square of the problem size.

On the other hand, contour enhancement in the case of a reaction-diffusion medium is a primitive operation. It is performed in all points of the medium simultaneously, therefore the complexity function does not depend on problem size.

In what follows, we attempt to:

  • Give examples and discuss the high behavioral complexity of biomolecular systems based on nonlinear dynamic mechanisms

  • Speculate on the assumption that the high behavioral complexity of biomolecular media is in close correlation with their capabilities in solving problems of high computational complexity

  • Give examples of complex computations performed by biomolecular media




Molecular Computing
Molecular Computing
ISBN: 0262693313
EAN: 2147483647
Year: 2003
Pages: 94

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net