On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics
From MaRDI portal
Publication:4314669
DOI10.2307/2275906zbMath0805.03047MaRDI QIDQ4314669
Publication date: 27 November 1994
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2275906
PRA; self-referential sentences; lower bounds for proof length; Hilbert-style calculi; proof speedup
03-02: Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
03F35: Second- and higher-order arithmetic and fragments
03F20: Complexity of proofs
Related Items
The lengths of proofs: Kreisel's conjecture and Gödel's speed-up theorem, Generalizing proofs in monadic languages (with a postscript by Georg Kreisel)., Deflationary truth and pathologies, Bounded arithmetic, proof complexity and two papers of Parikh, TRUTH AND SPEED-UP, Von Neumann, Gödel and Complexity Theory, 2005 Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '05
Cites Work