INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
From MaRDI portal
Publication:5082067
DOI10.1017/jsl.2021.75OpenAlexW3158765418WikidataQ113858283 ScholiaQ113858283MaRDI QIDQ5082067
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
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of proofs (03F20) Communication complexity, information complexity (68Q11)
Related Items (1)
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