Lectures on a Theory of Computation and Complexity over the Reals

TitleLectures on a Theory of Computation and Complexity over the Reals
Publication TypeTechnical Report
Year of Publication1989
AuthorsBlum, L.
Other Numbers564

These lectures discuss a new theory of computation and complexity which attempts to integrate key ideas from the classical theory in a setting more amenable to problems defined over continuous domains. The goal is to develop theoretical foundations for a theory of computational complexity for numerical analysis and scientific computation that might embody some of the naturalness and strengths of the classical theory.We highlight key aspects of the new theory as well as to give exposition, in this setting, of classical ideas and results. Indeed, one of our themes will be the comparison of results over the integers with results over the reals and complex numbers. Contrasting one theory with the other will help illuminate each, and give deeper understanding to such basic concepts as decidability, definability, computability and complexity.

Bibliographic Notes

ICSI Technical Report TR-89-065

Abbreviated Authors

L. Blum

ICSI Publication Type

Technical Report