×

Computational complexity of real functions. (English) Zbl 0498.03047


MSC:

03F60 Constructive and recursive analysis
03D15 Complexity of computation (including implicit computational complexity)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aberth, O., Analysis in the computable number field, J. ACM, 15, 275-299 (1968) · Zbl 0159.01201
[2] Aho, A. V.; Hopcroft, J. E.; Ulknan, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Cambridge, MA, Chapter 10
[3] Blum, M., A machine-independent theory of the complexity of recursive functions, J. ACM, 14, 322-366 (1967) · Zbl 0155.01503
[4] Constable, R. L., Type two computational complexity, (Proc. 5th ACM Symposium on Theory of Computing (1973)) · Zbl 0257.68036
[5] Grzegorczyk, A., On the definitions of computable real continuous functions, Fund. Math., 44, 61-71 (1957) · Zbl 0079.24801
[6] Grzegorczyk, A., Some approaches to constructive analysis, (Heyting, A., Constructivity in Mathematics (1959), North-Holland: North-Holland Reading, MA), 43-61
[7] Henrici, P.; Gargantini, I., Uniformly convergent algorithms for the simultaneous approximation of all zeros of a polynomial, (Dejon, B.; Henrici, P., Constructive Aspects of the Fundamental Theorem of Algebra (1969), Wiley-Interscience: Wiley-Interscience Amsterdam), 77-113 · Zbl 0194.46902
[8] Ko, K., Computational complexity of real functions and polynomial time approximations, Ph.D. Thesis, The Ohio State University, Columbus, Ohio (1979)
[9] K. Ko, The maximum value problem and NP real numbers, J. Comput. System Sci.; K. Ko, The maximum value problem and NP real numbers, J. Comput. System Sci. · Zbl 0481.03038
[10] Lacombe, D., Extension de la notion de fonction récursive sux fonctions d’une ou plusieurs variables réelles, and other notes, Comptes Rendus, 241, 1250-1252 (1955) · Zbl 0067.00205
[11] Lacombe, D., Les ensembles récursivement ouverts on fermès et leurs applications à l’analyse récursive, and other notes, Comptes Rendus, 245, 1040-1043 (1957) · Zbl 0078.00703
[12] Mostowski, A., On computable sequences, Fund. Math., 44, 37-51 (1957) · Zbl 0079.24702
[13] Myhill, J., Criteria of constructibility for real numbers, J. Symbolic Logic, 18, 7-10 (1953) · Zbl 0052.25101
[14] Pinkert, J. R., An exact method for finding the roots of a complex polynomial, ACM Trans. Math. Software, 2, 351-363 (1976) · Zbl 0341.65036
[15] Rice, H. G., Recursive real numbers, (Proc. Amer. Math. Soc., 5 (1954)), 784-791 · Zbl 0058.00602
[16] Rogers, H., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York · Zbl 0183.01401
[17] Rudin, W., Principles of Mathematical Analysis, ((1964), McGraw-Hill: McGraw-Hill New York), 141 · Zbl 0148.02903
[18] Sanin, N. A., Constructive Real Numbers and Function Spaces, (Mendelson, E. (1968), Amer. Math. Soc.: Amer. Math. Soc. New York)
[19] Specker, E., Nicht konstruktiv beweisbare Sätze der Analysis, J. Symbolic Logic, 14, 145-158 (1949) · Zbl 0033.34102
[20] Turing, A. M., On computable numbers, with an application to the Entscheidungs problem, (Proc. London Math. Soc., 42 (1937)), 230-265 · Zbl 0016.09701
[21] Wilf, H. S., A global bisection algorithm for computing the zeroes of polynomials in the complex plane, J. ACM, 25, 415-420 (1978) · Zbl 0378.30003
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.