Abstracts for the LGTDS workshop

ICGT Conference , Barcelona, October 2002


Complexity and dynamic systems: Tree-width, regularity and information flow

D. Seese

Institute AIFB
University Karlsruhe (TH)
D-76128 Karlsruhe
Germany
seese@aifb.uni-karlsruhe.de
Tel.: (+49) 721 / 608-6037
Fax: (+49) 721 / 69 37 17
http://www.aifb.uni-karlsruhe.de/CoM

Abstract

Dynamic systems play an important role in many areas of application, from biology, chemistry, economics, meteorology, artificial life, cellular automata, mathematics, physics and social sciences to control theory, from the movement of planets over weather prediction to engineering and everyday business life. During the last 15 or 20 years there has been a lot of success in the study of dynamic systems. It developed a new branch of complexity theory almost completely disjoint from computational complexity. Recently there were some successful attempts to prove computational complexity and undecidability results in this area. Nevertheless it remains the question, whether it is possible to merge the area of dynamic complexity with the area of computational complexity to a more unified complexity theory.

The talk will give a survey on results and problems, which result from an analysis of some of these problems using tools from computational complexity theory and graph theory. Its main focus will be on an investigation of structural reasons for high and low complexity. With respect to this question the structure of information flow graphs underlying the algorithms of several dynamic systems is investigated. It is shown that these results fit well in a structural classification of the complexity of problems in algorithmic graph theory.

Together with the results some open problems in this area are discussed.

 The results were obtained together with Frank Schlottmann (see [SchSee02], [SeeSch02] and [SeeSch02b])

 References:

[SchSee02] F. Schlottmann, D. Seese: The building blocks of complexity: a unified criterion and selected applications in economics and finance, April 2002, Material for a series of lectures at the School of Finance and Economics of the University of Technology in Sydney, at the School of Mathematics and Statistics of the University of Sydney and at the Sydney Financial Mathematics Workshop http://www.qgroup.org.au/SFMW/ .

[SeeSch02a] D. Seese, F. Schlottmann: Large grids and local information flow as a reason for high complexity; in G. Frizelle, H. Richards Eds. Tackling industrial complexity: the ideas that make a difference, Proceedings of the 2002 conference of the Manufacturing Complexity Network, University of Cambridge, UK 9-10 April 2002, pp. 193 - 207, http://www-mmd.eng.cam.ac.uk/mcn .

[SeeSch02b] D. Seese, F. Schlottmann: Structural reasons for high complexity: A survey on results and problems, in preparation.