×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
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 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, () · 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, (), 43-61
[7] Henrici, P.; Gargantini, I., Uniformly convergent algorithms for the simultaneous approximation of all zeros of a polynomial, (), 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., to appear. · Zbl 0481.03038
[10] Lacombe, D.; Lacombe, D.; Lacombe, D.; Lacombe, D., Extension de la notion de fonction récursive sux fonctions d’une ou plusieurs variables réelles, and other notes, Comptes rendus, Comptes rendus, Comptes rendus, Comptes rendus, 241, 1250-1252, (1955) · Zbl 0067.00205
[11] Lacombe, D.; Lacombe, D.; Lacombe, D., LES ensembles récursivement ouverts on fermès et leurs applications à l’analyse récursive, and other notes, Comptes rendus, Comptes rendus, 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, (), 784-791 · Zbl 0058.00602
[16] Rogers, H., Theory of recursive functions and effective computability, (1967), McGraw-Hill New York · Zbl 0183.01401
[17] Rudin, W., Principles of mathematical analysis, (), 141
[18] Sanin, N.A., Constructive real numbers and function spaces, ()
[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, (), 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. 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.