Abstract
Three formulations of computable real numbers based on the concepts of Cauchy sequences, Dedekind cuts, and the binary expansions have been carefully studied. We extend the definitions to recursively enumerable real numbers, and some complexity-bounded classes of real numbers. In particular, polynomial time and nondeterministic polynomial time computable real numbers are defined and compared. Although the three definitions are equivalent for the class of recursive real numbers, they are not equivalent for other classes of real numbers. It seems that the definition based on the concept of Cauchy sequences is the most general one.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Book, Tally languages and complexity classes,Information and Control, 26, 186–183 (1974).
P. Berman, Relationship between density and deterministic complexity of NP-complete languages, Fifth International Coll. Auto. Lang. Programming,Lecture Notes in Computer Science, 62, Springer, New York (1978) pp. 63–71.
A. Grzegorcyzk, Some approaches to constructive analysis, inConstructivity in Mathematics, A. Heyting ed., North-Holland, Amsterdam (1956) pp. 43–61.
J. Hartmanis and H. B. Hunt, III, The LBA problem and its importance in the theory of computing,SIAM-AMS Proc., 7, 1–26 (1974).
K. Ko, Computational complexity of real functions and polynomial time approximation, Ph.D. Thesis, The Ohio State University, Columbus, Ohio (1979).
K. Ko, The maximum value problem and NP real numbers,J. Comput. System Sci., 24, 15–35 (1982).
K. Ko and H. Friedman, Computational complexity of real functions,Theoret. Comput. Sci., 20, 323–352 (1982).
R. Ladner, N. Lynch and A. L. Selman, A comparison of polynomial-time reducibilities,Theoret. Comput. Sci., 1, 103–213 (1975).
A. Mostowski, On computable sequences,Fund. Math., 44, 37–51 (1957).
A. Mostowski, On various degrees of constructivism, inConstructivity in Mathematics, A. Heyting, ed., North Holland, Amsterdam, (1959), pp. 178–194.
H. G. Rice, Recursive real numbers,Proc. Amer. Math. Soc., 5, 784–791 (1954).
R. M. Robinson, Review of R. Peter's book, Rekursive Funktionen,J. Symb. Log., 16, 280–282 (1951).
H. Rogers, Jr.,Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967).
J. I. Seiferas, M. I. Fischer and A. R. Meyer, Separating nondeterministic time complexity classes,J. Assoc. Comput. Mach., 25, 146–167 (1978).
A. L. Selman,P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP,Math. Systems Theory, 13, 55–65 (1979).
A. L. Selman, Some observations on NP real numbers and P-selective sets,J. Comput. System Sci., 23, 326–332 (1981).
E. Specker, Nicht konstruktiv beweisbare Sätze der Analysis,J. Symb. Log., 14, 145–158 (1949).
L. J. Stockmeyer. The polynomial time hierarchy,Theoret. Comput. Sci., 3, 1–22 (1977).
A. M. Turing, On computable numbers, with an application to the Entscheidungs problems,Proc. London Math. Soc., 42, 430–265 (1937).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ko, KI. On the definitions of some complexity classes of real numbers. Math. Systems Theory 16, 95–109 (1983). https://doi.org/10.1007/BF01744572
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01744572