Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-22T14:05:06.532Z Has data issue: false hasContentIssue false
  • English
  • Français

Von Neumann, Gödel and Complexity Theory

Published online by Cambridge University Press:  15 January 2014

Alasdair Urquhart
Alasdair Urquhart*
Affiliation:
Department of Computer Science, 10 King's College Road, University of Toronto, Toronto, Ontario M5S 3G4, Canada. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Around 1989, a striking letter written in March 1956 from Kurt Gödel to John von Neumann came to light. It poses some problems about the complexity of algorithms; in particular, it asks a question that can be seen as the first formulation of the P = ? NP question. This paper discusses some of the background to this letter, including von Neumann's own ideas on complexity theory. Von Neumann had already raised explicit questions about the complexity of Tarski's decision procedure for elementary algebra and geometry in a letter of 1949 to J. C. C. McKinsey. The paper concludes with a discussion of why theoretical computer science did not emerge as a separate discipline until the 1960s.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 16 , Issue 4 , December 2010 , pp. 516 - 530
Copyright
Copyright © Association for Symbolic Logic 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Agrawal, Manindra, Kayal, Neeraj, and Saxena, Nitin, PRIMES is in P, The Annals of Mathematics, vol. 160 (2004), pp. 781–793.Google Scholar
[2] Aspray, William, John von Neumann and the origins of modern computing, The MIT Press, 1990.Google Scholar
[3] Buss, Samuel R., On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics, The Journal of Symbolic Logic, vol. 59 (1994), pp. 737–756.CrossRefGoogle Scholar
[4] Buss, Samuel R., On Gödel's theorems on lengths of proofs II: Lower bounds for recognizing k symbol provability, Feasible mathematics II (Clote, Peter and Remmel, Jeffrey, editors), Birkhäuser, 1995, pp. 57–90.CrossRefGoogle Scholar
[5] Caviness, B. F. and Johnson, J. R. (editors), Quantifier elimination and cylindrical algebraic decomposition, Texts and Monographs in Symbolic Comptutation, Springer-Verlag, Vienna and New York, 1998.CrossRefGoogle Scholar
[6] Clote, Peter and Krajíček, Jan (editors), Arithmetic, proof theory, and computational complexity, Oxford University Press, 1993.CrossRefGoogle Scholar
[7] Cobham, Alan, The intrinsic computational difficulty of functions, Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science (Bar-Hillel, Yehoshua, editor), North-Holland, 1964, pp. 24–30.Google Scholar
[8] Collins, George E., Tarski's decision method for elementary algebra, Summer Institute for Symbolic Logic, Cornell University 1957, Institute for Defense Analyses, Communications Research Division, second ed., 1960, summaries of talks presented, pp. 64–70.Google Scholar
[9] Collins, George E., Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Automata theory and formal languages, Lecture Notes in Computer Science, vol. 33, Springer Verlag, 1975, reprinted in [5], pp. 85-121, pp. 134–183.Google Scholar
[10] Cook, Stephen A., The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of Computing, 1971, pp. 151–158.Google Scholar
[11] Craig, William, On axiomatizability within a system, The Journal of Symbolic Logic, vol. 18 (1953), pp. 30–32.Google Scholar
[12] Davis, Martin, A program for Presburger arithmetic, Summer Institute for Symbolic Logic, Cornell University 1957, Institute for Defense Analyses, Communications Research Division, second edition ed., 1960, summaries of talks presented, pp. 215–223.Google Scholar
[13] Davis, Martin, The prehistory and early history of automated deduction, Automation of reasoning, volume 1: Classical papers on computational logic 1957–1966 (Siekmann, Jörg and Wrightson, Graham, editors), Springer-Verlag, 1983, pp. 1–28.Google Scholar
[14] Edmonds, Jack, Paths, trees, and flowers, Canadian Journal of Mathematics, vol. 17 (1965), pp. 449–467.CrossRefGoogle Scholar
[15] Ehrenfeucht, Andrzej and Mycielski, Jan, Abbreviating proofs by adding new axioms, Bulletin of the American Mathematical Society, vol. 77 (1971), pp. 366–367.Google Scholar
[16] Feferman, Anita Burdman and Feferman, Solomon, Alfred Tarski: Life and logic, Cambridge University Press, 2004.Google Scholar
[17] Feferman, Solomon, Dawson, John W. Jr., Goldfarb, Warren, Parsons, Charles, and Sieg, Wilfried (editors), Kurt Gödel. Collected works, volume V: Correspondence H–Z, Oxford University Press, 2003.Google Scholar
[18] Feferman, Solomon, Dawson, John W. Jr., Kleene, Stephen C., Moore, Gregory H., Solovay, Robert M., and van Heijenoort, Jean (editors), Kurt Gödel. Collected works, volume I: Publications 1929–1936, Oxford University Press, 1986.Google Scholar
[19] Fischer, M. J. and Rabin, M. O., Super-exponential complexity of Presburger arithmetic, Complexity of computations, SIAM–AMS Proceedings, vol. 7, 1974, reprinted in [5], pp. 122–135, pp. 27–41.Google Scholar
[20] Gödel, Kurt, Über die Länge von Beweisen, Ergebnisse eines mathematischen Kolloquiums, vol. 7 (1936), pp. 23–24, reprinted in [18] with facing English translation, entitled “On the Length of Proofs”.Google Scholar
[21] Halmos, P. R., I want to be a mathematician: An automathography, Springer-Verlag, 1985.Google Scholar
[22] Hartmanis, Juris, Observations about the development of theoretical computer science, Annals of the History of Computing, vol. 3 (1981), pp. 42–51.Google Scholar
[23] Hartmanis, Juris, Gödel, von Neumann and the P = ? NP problem, Bulletin of the European Association for Theoretical Computer Science, vol. 38 (1989), pp. 101–107.Google Scholar
[24] Knuth, Donald E., The IBM 650: An appreciation from the field, Annals of the History of Computing, vol. 8 (1986), pp. 50–55, reprinted in [25], pp. 227-239.Google Scholar
[25] Knuth, Donald E., Selected papers on computer science, CSLI Lecture Notes 59, CSLI Publications and Cambridge University Press, 1996.Google Scholar
[26] Krajíček, Jan, On the number of steps in proofs, Annals of Pure and Applied Logic, vol. 41 (1989), pp. 153–178.CrossRefGoogle Scholar
[27] Levin, Leonid, Universal sorting problems, Problems of Information Transmission, vol. 9 (1973), pp. 265–266.Google Scholar
[28] McKinsey, J. C. C., Introduction to the theory of games, The RAND Series, McGraw-Hill, New York, Toronto, London, 1952.Google Scholar
[29] Mostowski, Andrzej, Sentences undecidable in formalized arithmetic: An exposition of the theory of Kurt Gödel, North-Holland, Amsterdam, 1952.Google Scholar
[30] Nasar, Sylvia, A beautiful mind: A biography of John Forbes Nash, Jr., winner of the Nobel Prize in Economics, 1994, Simon and Schuster, 1998.Google Scholar
[31] Parikh, Rohit J., Introductory note to 1936a, Kurt Gödel, Collected works, volume I: Publications 1929–1936, Oxford University Press, 1986, pp. 394–396.Google Scholar
[32] Quine, W. V., Autobiography of W. V. Quine, The philosophy of W. V. Quine (Hahn, Lewis Edwin and Schilpp, Paul Arthur, editors), The Library of Living Philosophers, vol. XVIII, Open Court Publishing Company, 1986, pp. 1–48.Google Scholar
[33] Rabin, Michsael O., Mathematical theory of automata, Proceedings of the 19th ACM Symposium in Applied Mathematics, 1966, pp. 153–175.Google Scholar
[34] Rédei, Miklós (editor), John von Neumann: Selected letters, History of Mathematics, vol. 27, American Mathematical Society, 2005.Google Scholar
[35] Shannon, Claude E., The synthesis of two-terminal switching circuits, Bell System Technical Journal, vol. 28 (1949), pp. 59–98, reprinted in [38].Google Scholar
[36] Sheridan, Peter, The Fortran automatic coding system, Summer Institute for Symbolic Logic, Cornell University 1957, Institute for Defense Analyses, Communications Research Division, second ed., 1960, summaries of talks presented, pp. 425–426.Google Scholar
[37] Sipser, Michael, The history and status of the P versus NP question, Proceedings of the 24th annual ACM Symposium on the Theory of Computing, 1992, pp. 603–618.Google Scholar
[38] Sloane, N. J. A. and Wyner, Aaron D. (editors), Claude E. Shannon. Collected papers, IEEE Press, 1993.Google Scholar
[39] Tarski, Alfred, A decision method for elementary algebra and geometry, second revised ed., University of California Press, 1951, prepared for publication with the assistance of J. C. C. McKinsey. First edition published in 1948 as RAND report R-109, RAND Corporation, Santa Monica, CA.CrossRefGoogle Scholar
[40] Taub, A. H. (editor), John von Neumann. Collected works volume V: Design of computers, theory of automata and numerical analysis, Pergamon Press, 1961.Google Scholar
[41] Trakhtenbrot, B.A., A survey of Russian approaches to Perebor (Brute-Force Search) algorithms, Annals of the History of Computing, vol. 6 (1984), pp. 384–440.Google Scholar
[42] von Neumann, John, The general and logical theory of automata, Cerebral mechanisms in behaviour–the Hixon symposium, John Wiley, New York, 1948, reprinted in [40], pp. 288–328.Google Scholar
[43] von Neumann, John, Theory of self-reproducing automata, University of Illinois Press, Urbana and London, 1966, edited and completed by Arthur W. Burks.Google Scholar