Monotone simulations of non-monotone proofs.
From MaRDI portal
Publication:1872729
DOI10.1016/S0022-0000(02)00020-XzbMath1034.03054OpenAlexW2158912767MaRDI QIDQ1872729
Pavel Pudlák, Albert Atserias, Nicola Galesi
Publication date: 14 May 2003
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(02)00020-x
Related Items (10)
Proofs with monotone cuts ⋮ Expander Construction in VNC1 ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ On \(\epsilon\)-sensitive monotone computations ⋮ On theories of bounded arithmetic for \(\mathrm{NC}^1\) ⋮ A sorting network in bounded arithmetic ⋮ Algebraic proofs over noncommutative formulas ⋮ Substitution Frege and extended Frege proof systems in non-classical logics ⋮ Proof complexity of monotone branching programs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sorting in \(c \log n\) parallel steps
- The intractability of resolution
- Proof theory. 2nd ed
- The gap between monotone and non-monotone circuit complexity is exponential
- Monotone Proofs of the Pigeon Hole Principle
- Short monotone formulae for the majority function
- Polynomial size proofs of the propositional pigeonhole principle
- The relative efficiency of propositional proof systems
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for resolution and cutting plane proofs and monotone computations
- On the computational content of intuitionistic propositional proofs
This page was built for publication: Monotone simulations of non-monotone proofs.
