Proofs with monotone cuts
From MaRDI portal
Publication:2888631
DOI10.1002/malq.201020071zbMath1256.03060MaRDI QIDQ2888631
Publication date: 1 June 2012
Published in: Mathematical Logic Quarterly (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/malq.201020071
03F20: Complexity of proofs
Cites Work
- A sorting network in bounded arithmetic
- Sorting in \(c \log n\) parallel steps
- Monotone simulations of non-monotone proofs.
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Short monotone formulae for the majority function
- Polynomial size proofs of the propositional pigeonhole principle
- Syntactical and semantical properties of simple type theory
- Lower bounds to the size of constant-depth propositional proofs
- Unnamed Item
- Unnamed Item
- Unnamed Item