×

zbMATH — the first resource for mathematics

On the definitions of some complexity classes of real numbers. (English) Zbl 0529.03016

MSC:
03D15 Complexity of computation (including implicit computational complexity)
03D30 Other degrees and reducibilities in computability and recursion theory
03F60 Constructive and recursive analysis
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R. Book, Tally languages and complexity classes,Information and Control, 26, 186–183 (1974). · Zbl 0287.68029 · doi:10.1016/S0019-9958(74)90473-2
[2] 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.
[3] A. Grzegorcyzk, Some approaches to constructive analysis, inConstructivity in Mathematics, A. Heyting ed., North-Holland, Amsterdam (1956) pp. 43–61.
[4] 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). · Zbl 0301.68056
[5] K. Ko, Computational complexity of real functions and polynomial time approximation, Ph.D. Thesis, The Ohio State University, Columbus, Ohio (1979).
[6] K. Ko, The maximum value problem and NP real numbers,J. Comput. System Sci., 24, 15–35 (1982). · Zbl 0481.03038 · doi:10.1016/0022-0000(82)90053-8
[7] K. Ko and H. Friedman, Computational complexity of real functions,Theoret. Comput. Sci., 20, 323–352 (1982). · Zbl 0498.03047 · doi:10.1016/S0304-3975(82)80003-0
[8] R. Ladner, N. Lynch and A. L. Selman, A comparison of polynomial-time reducibilities,Theoret. Comput. Sci., 1, 103–213 (1975). · Zbl 0321.68039 · doi:10.1016/0304-3975(75)90016-X
[9] A. Mostowski, On computable sequences,Fund. Math., 44, 37–51 (1957). · Zbl 0079.24702
[10] A. Mostowski, On various degrees of constructivism, inConstructivity in Mathematics, A. Heyting, ed., North Holland, Amsterdam, (1959), pp. 178–194. · Zbl 0088.25001
[11] H. G. Rice, Recursive real numbers,Proc. Amer. Math. Soc., 5, 784–791 (1954). · Zbl 0058.00602 · doi:10.1090/S0002-9939-1954-0063328-5
[12] R. M. Robinson, Review of R. Peter’s book, Rekursive Funktionen,J. Symb. Log., 16, 280–282 (1951). · doi:10.2307/2267933
[13] H. Rogers, Jr.,Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967). · Zbl 0183.01401
[14] J. I. Seiferas, M. I. Fischer and A. R. Meyer, Separating nondeterministic time complexity classes,J. Assoc. Comput. Mach., 25, 146–167 (1978). · Zbl 0366.68038
[15] A. L. Selman,P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP,Math. Systems Theory, 13, 55–65 (1979). · Zbl 0415.03031 · doi:10.1007/BF01744288
[16] A. L. Selman, Some observations on NP real numbers and P-selective sets,J. Comput. System Sci., 23, 326–332 (1981). · Zbl 0486.03020 · doi:10.1016/0022-0000(81)90068-4
[17] E. Specker, Nicht konstruktiv beweisbare Sätze der Analysis,J. Symb. Log., 14, 145–158 (1949). · Zbl 0033.34102 · doi:10.2307/2267043
[18] L. J. Stockmeyer. The polynomial time hierarchy,Theoret. Comput. Sci., 3, 1–22 (1977). · Zbl 0353.02024 · doi:10.1016/0304-3975(76)90061-X
[19] A. M. Turing, On computable numbers, with an application to the Entscheidungs problems,Proc. London Math. Soc., 42, 430–265 (1937). · Zbl 0016.09701 · doi:10.1112/plms/s2-42.1.230
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.