Publication Details
Title: Lectures on a Theory of Computation and Complexity over the Reals
Author: L. Blum
Group: ICSI Technical Reports
Date: December 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-65.pdf
Overview:
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 Information:
ICSI Technical Report TR-89-065
Bibliographic Reference:
L. Blum. Lectures on a Theory of Computation and Complexity over the Reals. ICSI Technical Report TR-89-065, December 1989
Author: L. Blum
Group: ICSI Technical Reports
Date: December 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-65.pdf
Overview:
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 Information:
ICSI Technical Report TR-89-065
Bibliographic Reference:
L. Blum. Lectures on a Theory of Computation and Complexity over the Reals. ICSI Technical Report TR-89-065, December 1989