An Introduction to Lower Bounds on Resolution Proof Systems

DOI10.4036/iis.2015.L.02zbMath1486.03097OpenAlexW2185133332MaRDI QIDQ5135261

Kazuhisa Seto

Publication date: 19 November 2020

Published in: Interdisciplinary Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4036/iis.2015.l.02

zbMATH Keywords

sizeresolutiontradeoffsproof complexityspace

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards NP-P via proof complexity and search
• A lower bound on the size of resolution proofs of the Ramsey theorem
• Resolution proofs of generalized pigeonhole principles
• A simplified way of proving trade-off results for resolution
• The intractability of resolution
• Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
• Resolution lower bounds for perfect matching principles
• Pebble Games, Proof Complexity, and Time-Space Trade-offs
• On the Relative Strength of Pebbling and Resolution
• Space Complexity in Propositional Calculus
• Many hard examples for resolution
• Twelve Problems in Proof Complexity
• Hard examples for resolution
• The relative efficiency of propositional proof systems
• Short proofs are narrow—resolution made simple
• Space complexity of random formulae in resolution
• The Complexity of Propositional Proofs
• Narrow Proofs May Be Spacious:Separating Space and Width in Resolution
• Time-space tradeoffs in resolution
• The Complexity of Propositional Proofs
• Strong ETH holds for regular resolution
• Resolution lower bounds for the weak pigeonhole principle

This page was built for publication: An Introduction to Lower Bounds on Resolution Proof Systems