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 arc 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 parallel 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. 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 . It is closely related to work done by A. BEN-HUR, H. SIEGELMANN, and S. FISHMAN [12, 11].
Gori, M., & Meer, K. (2002). A step towards a complexity theory for analog systems. MATHEMATICAL LOGIC QUARTERLY, 48(Supplemento 1), 45-58 [10.1002/1521-3870(200210)48:1+<45::AID-MALQ45>3.0.CO;2-7].
|Titolo:||A step towards a complexity theory for analog systems|
|Citazione:||Gori, M., & Meer, K. (2002). A step towards a complexity theory for analog systems. MATHEMATICAL LOGIC QUARTERLY, 48(Supplemento 1), 45-58 [10.1002/1521-3870(200210)48:1+<45::AID-MALQ45>3.0.CO;2-7].|
|Appare nelle tipologie:||1.1 Articolo in rivista|
File in questo prodotto: