INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH

DOI10.1017/JSL.2021.75OpenAlexW3158765418WikidataQ113858283 ScholiaQ113858283MaRDI QIDQ5082067

Jan Krajíček

Publication date: 15 June 2022

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

Full work available at URL: https://arxiv.org/abs/2104.04711

zbMATH Keywords

propositional proof systemsproof searchalgorithmic information

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of proofs (03F20) Communication complexity, information complexity (68Q11)

Related Items (1)

ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on SAT algorithms and proof complexity
• Short propositional refutations for dense random 3CNF formulas
• The intractability of resolution
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• Algorithmic information theory
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Randomness conservation inequalities; information and independence in mathematical theories
• The relative efficiency of propositional proof systems
• On Interpolation and Automatization for Frege Systems
• Proof Complexity
• Information-Theoretic Limitations of Formal Systems
• Diagonalization in proof complexity
• Automating Resolution is NP-Hard
• 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
• Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
• Implicit proofs
• Consequences of the provability of NP ⊆ P/poly
• Logical basis for information theory and probability theory

This page was built for publication: INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH