Manuel Blum
Abstract
The number of steps required to compute a function depends, in general, on the type of computer that is used, on the choice of computer program, and on the input-output code. Nevertheless, the results obtained in this paper are so general as to be nearly independent of these considerations.
A function is exhibited that requires an enormous number of steps to be computed, yet has a “nearly quickest” program: Any other program for this function, no matter how ingeniously designed it may be, takes practically as many steps as this nearly quickest program.
A different function is exhibited with the property that no matter how fast a program may be for computing this function another program exists for computing the function very much faster.
- 1 ARBIB, M. A., AND BLUM, M. Machine dependence of degrees of difficulty. Proc. Amer. Math. Soc. 16, 3 (June 1965), 442-447.Google Scholar
- 2 HARTMANIS, J., AND STEARNS, R. E. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 5 (May 1965), 285-306.Google Scholar
- 3 ----- ,AND .... . Computational complexity of reeursive sequences. Proc. 5th Annual Symp. on Switching Theory and Logical Design, Princeton, N. J., 1964.Google Scholar
- 4 MYHILL, J. Linear bounded automata. WADD Tech. Note 60-165, U. of Pennsylvania Rep. No. 60-22 (June 1960).Google Scholar
- 5 RABIN, M. O. Degree of difficulty of computing a function and a partial ordering of recursive sets. Tech. Rep. No. 2, Hebrew U., Jerusalem, Israel (April 1960).Google Scholar
- 6 ---. Real time computation. Israel J. Math. I (1963), 203-211.Google Scholar
- 7 RITCHIE, R.W. Classes of predictably computable functions. Trans. Amer. Math. Soc. I06, 1 (June 1963), 139-173.Google Scholar
- 8 BOOERS, It., JR. GSdel numberings of partiM reeursive functions. J. Symbolic Logic 23, 3 (Sept. 1958), 331-341.Google Scholar
- 9 ----. Recursive functions and effective computability. McGraw-Hill, New York (in press).Google Scholar
- 10 YAMADA, H. Real-time computation and recursive functions not real-time computable. IR, E Trans. EC-11, 66 (Dec. 1962), 753-760.Google Scholar
- 11 COBHAM, A. The intrinsic computational complexity of functions. Proc. 1964 Int. Congress on Logic, Methodology and Philosophy of Science. North-Holland, Amsterdam, 1965, 24-30.Google Scholar
- 12 COOKE, S. A. Otl the minimum computation time of functions. Bell Labs. Rep. BL-41, 1966.Google Scholar
- 13 WINOGRAD, S. On the time required to perform multiplication. IBM Res. Rep. RC-1564, 1966.Google Scholar
Index Terms
- A Machine-Independent Theory of the Complexity of Recursive Functions
Recommendations
On Almost Everywhere Complex Recursive Functions
Let h be a recursive function. A partial recursive function ψ is i.o. (infinitely often) h-complex if every program for ψ requires more than h(χ) steps to compute ψ(χ) for infinitely many inputs χ. A more stringent notion is that of ψ being a.e. (almost ...
Bent functions embedded into the recursive framework of $${\mathbb{Z}}$$ -bent functions
Suppose that n is even. Let $${\mathbb{F}_2}$$ denote the two-element field and $${\mathbb{Z}}$$ the set of integers. Bent functions can be defined as 1-valued functions on $${\mathbb{F}_2^n}$$ with 1-valued Fourier transform. More generally we call a mapping f on $${\mathbb{F}_2^n}$$ a $${\mathbb{Z}}$$ -bent function if both f and its ...
Comments