The Computational Complexity of Evolving Systems

Abstract

Evolving systems are systems that change over time. Examples of evolving systems are computers with soft-and hardware upgrades and dynamic networks of computers that communicate with each other, but also colonies of cooperating organisms or cells within a single organism. In this research, several models are designed that represent evolving systems in a suitable fashion. The causes of the changes are not taken into account for these models. One of these models uses a sequence of objects to model an evolving system. The objects in a sequence represent snapshots of an evolving system, taken one after the other.

The relationship between the amount of available time and memory and the efficiency with which computer systems perform their tasks has been well studied. The influence of changes in a system on their efficiency is unknown. In this research, the relationship between changes of an evolving computer system and the efficiency of the system is studied. A whole new theory is developed to formulate and better understand this relationship and related problems. The amount of change in a system is measured by determining the complexity of the individual components in a sequence that represents the evolving system. In theory, evolving systems possess "super-Turing" computational power, i.e., they are powerful enough to solve any problem. By imposing restrictions on the size of the changes, the theoretical power is reduced to a more realistic scale. The results proved in the thesis illustrate that many methods and techniques that are used to prove results in the classical complexity theory can be used, with the necessary modifications, to prove similar results in the complexity theory of evolving systems.