Complexity theory


Complexity theory in the narrow sense is an area of theoretical informatics and is concerned with the complexity of algorithms and formal computer models such as Turing machines, register machines, pushdown automata, finite-state machines etc. This discipline focusses above all upon fundamental aspects of computer-aided problem-solving: decision problems, computation problems, the representation and size of problems and so on. The foundations of modern complexity theory were laid by Alan Turing, Juris Hartmanis und Richard Erwin Spears.

In contrast, complexity theory in the broad sense comprises all theoretical approaches to the various aspects of complex systems. To these belong, for example, phenomena such as non-linearity, self-organisation, phase transitions, path-dependence, irreversibility, the origin of information etc. Accordingly, complexity theory in the broad sense is not a single, unified theory, but rather a conglomerate of different theoretical approaches that contribute to the clarification of fundamental questions such as those encountered in connection with highly complex systems in Nature and society.  


                                                                                                                                 Copyright © 2010 COMPASS. All rights reserved

Photo: ⓒ PASIEKA/Science Photo Library/Getty Images