On transformations of constant depth propositional proofs
From MaRDI portal
Publication:2311211
DOI10.1016/j.apal.2019.05.002OpenAlexW2945126541WikidataQ113880327 ScholiaQ113880327MaRDI QIDQ2311211
Arnold Beckmann, Samuel R. Buss
Publication date: 10 July 2019
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://cronfa.swan.ac.uk/Record/cronfa50215
Structure of proofs (03F07) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Discrete mathematics in relation to computer science (68R99) Complexity of proofs (03F20)
Cites Work
- Exponential lower bounds for the pigeonhole principle
- An exponential separation between the parity principle and the pigeonhole principle
- Separation results for the size of constant-depth propositional proofs
- Quantified propositional calculi and fragments of bounded arithmetic
- Lower bounds to the size of constant-depth propositional proofs
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
This page was built for publication: On transformations of constant depth propositional proofs
