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.