On the minimum computation time of functions
HTML articles powered by AMS MathViewer
- by Stephen A. Cook and Stȧl O. Aanderaa PDF
- Trans. Amer. Math. Soc. 142 (1969), 291-314 Request permission
References
-
A. J. Atrubin, A one-dimensional real-time iterative multiplier, IEEE Trans. Electronic Computers EC-14, No. 3 (1965), 394-399.
- Alan Cobham, The intrinsic computational difficulty of functions, Logic, Methodology and Philos. Sci. (Proc. 1964 Internat. Congr.), North-Holland, Amsterdam, 1965, pp. 24–30. MR 0207561 S. N. Cole, Real-time computation by iterative arrays of finite-state machines, Doctoral Thesis, and Report BL-36, Computation Laboratory, Harvard Univ., Cambridge, Mass., 1964. S. A. Cook, On the minimum computation time of functions, Doctoral Thesis, Harvard Univ., Cambridge, Mass., 1966.
- Patrick C. Fischer, Generation of primes by a one-dimensional real-time iterative array, J. Assoc. Comput. Mach. 12 (1965), 388–394. MR 186506, DOI 10.1145/321281.321290
- J. Hartmanis and R. E. Stearns, On the computational complexity of algorithms, Trans. Amer. Math. Soc. 117 (1965), 285–306. MR 170805, DOI 10.1090/S0002-9947-1965-0170805-7 F. C. Hennie, On-line Turing machine computations, IEEE Trans. Electronic Computers EC-15, No. 1 (1966), 35-44.
- F. C. Hennie, One-tape, off-line Turing machine computations, Information and Control 8 (1965), 553–578. MR 191769, DOI 10.1016/S0019-9958(65)90399-2
- Robert McNaughton, The theory of automata, a survey, Advances in Computers, Vol. 2, Academic Press, New York, 1961, pp. 379–421. MR 0136487
- Michael O. Rabin, Real time computation, Israel J. Math. 1 (1963), 203–211. MR 163849, DOI 10.1007/BF02759719
- A. Schönhage, Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 1 (1966), 182–196 (German, with English summary). MR 208868, DOI 10.1007/bf02234362
- J. C. Shepherdson and H. E. Sturgis, Computability of recursive functions, J. Assoc. Comput. Mach. 10 (1963), 217–255. MR 151374, DOI 10.1145/321160.321170
- A. L. Toom, The complexity of a scheme of functional elements simulating the multiplication of integers, Dokl. Akad. Nauk SSSR 150 (1963), 496–498 (Russian). MR 0156494 S. Winograd, On the time required to perform multiplication, J. Assoc. Comput. Mach. 14 (1967), 793-802.
Additional Information
- © Copyright 1969 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 142 (1969), 291-314
- MSC: Primary 94.40
- DOI: https://doi.org/10.1090/S0002-9947-1969-0249212-8
- MathSciNet review: 0249212