ALCOMFT-TR-01-191

Marco Gori and Klaus Meer
A step towards a complexity theory for dynamical systems
Århus. Work package 4. December 2001.

Abstract: Recent years have seen an increasing interest in the study of continuous-time computational models. However, not so much has been done with respect to setting up a complexity theoretic framework for such models. The present paper intends to go a step into this direction. We consider problems over the real numbers which we try to relate to Lyapunov theory for dynamical systems: The global minimizers of particular energy functions are supposed to give solutions of the problem. The structure of such energy functions leads to the introduction of problem classes U and NU; for the systems we are considering they parallelize the classical complexity classes P and NP. We then introduce a notion of reducibility among problems and show existence of complete problems for NU and for PU, a polynomial hierarchy of continuous-time problems.

Postscript file: ALCOMFT-TR-01-191.ps.gz (92 kb).