New formally undecidable propositions: Non-trivial lower bounds on proof complexity and related theorems

DOI10.1016/0304-3975(91)90272-4zbMath0728.03031OpenAlexW2004178012MaRDI QIDQ804570

Horst Luckhardt

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90272-4

zbMATH Keywords

consistencyGödel's second incompleteness theoremformally undecidable propositions

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Goedel speed-up and succinctness of language representations
• The varieties of arboreal experience
• Some applications of Henkin quantifiers
• Finite approach to the problem of optimizing theorem-proving algorithms
• The computational complexity of logical theories
• A Gödel Theorem on Network Complexity Lower Bounds
• Herbrand-Analysen zweier Beweise des Satzes von Roth: Polynomiale Anzahlschranken
• A theorem on shortening the length of proof in formal systems of arithmetic
• Gödel's Second incompleteness theorem for Q
• Redundancies in the Hilbert-Bernays derivability conditions for Gödel's second incompleteness theorem
• A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods
• Finite Partially‐Ordered Quantifiers
• Abbreviating proofs by adding new axioms

This page was built for publication: New formally undecidable propositions: Non-trivial lower bounds on proof complexity and related theorems