×

A note on A.E. h-complex functions. (English) Zbl 0694.68031

Summary: Rabin and Blum proved the existence of 0, 1-valued recursive functions which are arbitrarily hard to compute. Their proof was partially constructive in that they effectively gave a program for a function that required computation time exceeding a given bound. However, their proof that the function required the specified time contained a non- constructive element; here we show that that element is essential.

MSC:

68Q25 Analysis of algorithms and problem complexity
03D20 Recursive functions and relations, subrecursive hierarchies
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blum, M., A machine-independent theory of the complexity of recursive functions, J. Assoc. Comput. Mach., 14, 322-336 (1967) · Zbl 0155.01503
[2] Joseph, D.; Young, P., Independence results in computer science?, (Proceedings, 12th Annual Symposium on the Theory of Computation. Proceedings, 12th Annual Symposium on the Theory of Computation, Los Angeles, CA (1980)) · Zbl 0474.68046
[3] Lipton, R., Model theoretic aspects of computational complexity, (Proceedings, 19th Symposium on Foundations of Computer Science. Proceedings, 19th Symposium on Foundations of Computer Science, Ann Arbor, MI (1978))
[4] Machtey, M.; Young, P., An Introduction to the General Theory of Algorithms (1978), North-Holland: North-Holland New York · Zbl 0376.68027
[5] Rabin, M., Degree of Difficulty of Computing a Function, Hebrew University Technical Report, 2 (1960), Tel Aviv, Israel
[6] Rogers, H., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York · Zbl 0183.01401
[7] Schnorr, C. P., Does the computational speed-up concern programming?, (Proceedings, First International Conference on Automata, Languages, and Programming (1972)), 585-596
[8] Smith, C., A Note on Arbitrarily Complex Recursive Functions, (CS-TR1572 (1985), Department of Computer Science, University of Maryland: Department of Computer Science, University of Maryland College Park, MD) · Zbl 0651.03032
[9] Notre Dame J. Formal Logic, in press.; Notre Dame J. Formal Logic, in press.
[10] Smullyan, R., Theory of Formal Systems, (Annals of Mathematic Studies, Vol. 47 (1961), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ) · Zbl 0097.24503
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.