Lifting lower bounds for tree-like proofs

DOI10.1007/s00037-013-0064-xzbMath1341.03087OpenAlexW2124396273MaRDI QIDQ475337

J. Herrera, Sumit K. Garg

Publication date: 26 November 2014

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-013-0064-x

zbMATH Keywords

computational complexityproof complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Cites Work

• Unnamed Item
• Unnamed Item
• Exponential lower bounds for the pigeonhole principle
• The intractability of resolution
• Bounded arithmetic and the polynomial hierarchy
• An exponential lower bound for the size of monotone real circuits
• Non-automatizability of bounded-depth Frege proofs
• Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
• Short proofs are narrow—resolution made simple
• Parity, circuits, and the polynomial-time hierarchy
• Quantified propositional calculi and fragments of bounded arithmetic
• Bounds for proof-search and speed-up in the predicate calculus
• Lower bounds to the size of constant-depth propositional proofs
• Lower bounds for resolution and cutting plane proofs and monotone computations
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle

This page was built for publication: Lifting lower bounds for tree-like proofs