Resolution lower bounds for the weak functional pigeonhole principle.

DOI10.1016/S0304-3975(02)00453-XzbMath1050.03039MaRDI QIDQ1401365

Alexander A. Razborov

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

complexity of proofsresolution method

Mathematics Subject Classification ID

Related Items (9)

Resolution lower bounds for perfect matching principles ⋮ Width versus size in resolution proofs ⋮ Towards NP-P via proof complexity and search ⋮ A combinatorial characterization of resolution width ⋮ The treewidth of proofs ⋮ Unnamed Item ⋮ Resolution and the binary encoding of combinatorial principles ⋮ Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Resolution proofs of generalized pigeonhole principles
• The intractability of resolution
• Resolution lower bounds for perfect matching principles
• Many hard examples for resolution
• Hard examples for resolution
• Short proofs are narrow—resolution made simple
• Pseudorandom Generators in Propositional Proof Complexity
• Regular resolution lower bounds for the weak pigeonhole principle
• A Machine-Oriented Logic Based on the Resolution Principle
• A Computing Procedure for Quantification Theory

This page was built for publication: Resolution lower bounds for the weak functional pigeonhole principle.