|
NeuroCOLT
Technical Report NC-TR-02-126
2002-126
A Step towards a Complexity Theory for Dynamical Systems
Marco
Gori and Klaus Meer
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 ${\bf U}$ and ${\bf NU}$; for the systems we are considering
they parallelize the classical complexity classes
${\bf P}$ and ${\bf NP}$. We then introduce a notion of reducibility
among problems and show existence of
complete problems for ${\bf NU}$ and for ${\bf PU}$,
a polynomial hierarchy of continuous-time problems.
For previous work on the
computational capabilities of continuous-time systems see the surveys
by Cris Moore
and by Pekka Orponen. Our paper presents a step into the direction
of creating a general framework for a complexity theory of continuous-time
systems as outlined in Orponen's survey.
It is closely related to work done by Hava.T. Siegelmann, A. Ben-Hur
and Shmuel Fishman.
Download
Postscript
|