Gödel and Lengths of Proofs
Workshop on Celebrating 90 Years of Gödel's Incompleteness Theorems
University of Tübingen
Zoom presentation, July 8, 2021.
Abstract: The lengths of proofs and the complexity of proofs are of great interest due to its connections to complexity theory and theorem proving. Gödel was the first one to consider lengths of proofs. This talk will discuss three results in lengths of proofs related to Gödel's writings. The first is upper and lower bounds on the lengths of partial consistency statements (due to P. Pudlak and H. Friedman). The second is Gödel's separation of higher order theories of arithmetic. The third is a claim made by Gödel in a letter to von Neumann related to the question of whether P=NP.
Back to Sam Buss's publications page.