|
NeuroCOLT
Technical Report NC-TR-95-015
Computability
and complexity over the reals
Paolo
Boldi
University of Milan
Abstract
In this work, we sketch a (rather superficial) survey about
the problem of extending some of the classical notions from computation
and complexity theory to the non-classical realm of real numbers.
We first present an algorithmic approach, deeply studied by Blum,
Shub, Smale et al., and give a non-trivial separation result recently
obtained by Cucker. Then, we introduce some concepts from another
line of research, namely the one based on the notion of computable
real number.
Download Compressed
Postscript
|