Complexity theory on real numbers and functions.


Christoph Kreitz, Klaus Weihrauch.  
In A. B. Cremers & H.P. Kriegel, ed., 6th GI Conference on Theoretical Computer Science, LNCS 145, pp. 165174, Springer Verlag, 1983. 

Abstract 

The goal of this paper is to present a natural concept for computational
complexity of real numbers and functions. First we develop a complexity
theory on R corresponding to Blum's complexity theory on the recursive
functions. In order to obtain a successful definition of complexity we
represent real numbers by Cauchy sequences of dyadic numbers having a normed
convergence. We define the set of computable real numbers and an effective
numbering of this set. Complexity classes of real numbers are introduced and
it is shown that the most interesting statements of abstract complexity
theory hold analogously on computable real numbers.

Back to overview of papers 

Bibtex Entry 

@InProceedings{inp:KreitzWeihrauch83a, author = "Christoph Kreitz and Klaus Weihrauch", title = "Complexity theory on real numbers and functions", booktitle = "6$^{th}$ GI conference on Theoretical Computer Science", year = 1983, pages = "165174", editor = "A. B. Cremers and H. P. Kriegel", series = "Lecture Notes in Computer Science", volume = 145, publisher = "Springer Verlag" } 