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

DOI10.1016/0304-3975(91)90272-4MaRDI QIDQ804570zbMATH OpenOpenAlexFDO

Authors 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

consistency[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=G%EF%BF%BD%EF%BF%BDdel%27s+second+incompleteness+theorem&go=Go G��del's second incompleteness theorem]formally undecidable propositions

Mathematics Subject Classification ID

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

Recommendations

• Gödel's third incompleteness theorem
• A direct proof of Gödel's incompleteness theorems
• On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics
• scientific article; zbMATH DE number 2222023
• Gödel's second incompleteness theorem: how it is derived and what it delivers

Cites work

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

Cited in

(1)

• scientific article; zbMATH DE number 6829288 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804570)