Von Neumann, Gödel and Complexity Theory

DOI10.2178/bsl/1294171130zbMath1226.03004OpenAlexW2084784291MaRDI QIDQ3067861

Alasdair Urquhart

Publication date: 13 January 2011

Published in: The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/bsl/1294171130

zbMATH Keywords

automataTarskicomplexity theoryGödelproof complexityhistory of mathematicsvon NeumannAbraham RobinsonMcKinseyP vs. NPearly computers

Mathematics Subject Classification ID

History of mathematics in the 20th century (01A60) Complexity of computation (including implicit computational complexity) (03D15) History of mathematical logic and foundations (03-03) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) History of computer science (68-03)

Related Items (1)

A Logical Autobiography

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the number of steps in proofs
• PRIMES is in P
• Sentences undecidable in formalized arithmetic. An exposition of the theory of Kurt Gödel
• On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics
• Paths, Trees, and Flowers
• Abbreviating proofs by adding new axioms
• On axiomatizability within a system

This page was built for publication: Von Neumann, Gödel and Complexity Theory