Monotone simulations of non-monotone proofs.

DOI10.1016/S0022-0000(02)00020-XzbMath1034.03054MaRDI 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

zbMATH Keywords

complexity of proofs

Mathematics Subject Classification ID

03F20: Complexity of proofs

Related Items

Characterizing Propositional Proofs as Noncommutative Formulas, Expander Construction in VNC1, 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, Expander construction in \(\mathrm{VNC}^1\), On \(\epsilon\)-sensitive monotone computations, Proofs with monotone cuts

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