A proof complexity conjecture and the incompleteness theorem

DOI10.1017/JSL.2023.69MaRDI QIDQ6885851zbMATH OpenFDO

Authors Jan Krajíček

Publication date 10 December 2025

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1017/JSL.2023.69

zbMATH Keywords

exponential timeGödel's incompleteness theoremproof complexity

Mathematics Subject Classification ID

Complexity of proofs (03F20) Gödel numberings and issues of incompleteness (03F40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites work

• Diagonalization in proof complexity
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 3557241 (Why is no real title available?)
• INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
• On axiomatizability within a system
• Proof Complexity

This page was built for publication: A proof complexity conjecture and the incompleteness theorem

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