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. 165-174, Springer Verlag, 1983.


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 = "165--174", editor = "A. B. Cremers and H. P. Kriegel", series = "Lecture Notes in Computer Science", volume = 145, publisher = "Springer Verlag" }