Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

On the minimum computation time of functions


Authors: Stephen A. Cook and Stȧl O. Aanderaa
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
Full-text PDF

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • [1] A. J. Atrubin, A one-dimensional real-time iterative multiplier, IEEE Trans. Electronic Computers EC-14, No. 3 (1965), 394-399.
  • [2] A. Cobham, The intrinsic computational difficulty of functions, Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science, North-Holland, Amsterdam, 1965, pp. 24-30. MR 0207561 (34:7376)
  • [3] 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.
  • [4] S. A. Cook, On the minimum computation time of functions, Doctoral Thesis, Harvard Univ., Cambridge, Mass., 1966.
  • [5] P. C. Fischer, Generation of primes by a one-dimensional real-time iterative array, J. Assoc. Comput. Mach. 12 (1965), 388-394. MR 0186506 (32:3966)
  • [6] J. Hartmanis and R. E. Stearns, On the computational complexity of algorithms, Trans. Amer. Math. Soc. 117 (1965), 285-306. MR 0170805 (30:1040)
  • [7] F. C. Hennie, On-line Turing machine computations, IEEE Trans. Electronic Computers EC-15, No. 1 (1966), 35-44.
  • [8] -, One-tape, off-line Turing machine computations, Information and Control 8 (1965), 553-578. MR 0191769 (32:9171)
  • [9] R. McNaughton, ``The theory of automata, a survey'' in Advances in computers, Vol. 2, F. L. Alt, editor, Academic Press, New York, 1961, pp. 379-421. MR 0136487 (24:B2520)
  • [10] M. O. Rabin, Real-time computation, Israel J. Math. 1 (1963), 203-211. MR 0163849 (29:1148)
  • [11] A. Schönhage, Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 1 (1966), 182-196. MR 0208868 (34:8676)
  • [12] J. C. Shepherdson, and H. H. Sturgis, Computability of recursive functions, J. Assoc. Comput. Mach. 10 (1963), 217-255. MR 0151374 (27:1359)
  • [13] A. L. Toom, The complexity of a scheme of functional elements realizing the multiplication of integers, Dokl. Akad. Nauk SSSR 150 (1963), 496-498=Soviet Math. Dokl. 4 (1963), 714-716. MR 0156494 (27:6417)
  • [14] S. Winograd, On the time required to perform multiplication, J. Assoc. Comput. Mach. 14 (1967), 793-802.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 94.40

Retrieve articles in all journals with MSC: 94.40


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1969-0249212-8
Article copyright: © Copyright 1969 American Mathematical Society

American Mathematical Society