Regular resolution lower bounds for the weak pigeonhole principle

DOI10.1007/s00493-004-0029-4zbMath1063.03044OpenAlexW2001378190MaRDI QIDQ558246

Ran Raz, Toniann Pitassi

Publication date: 5 July 2005

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-004-0029-4

zbMATH Keywords

complexity of resolution proofsweak pigeonhole principle

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (4)

Width versus size in resolution proofs ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Unnamed Item ⋮ Propositional proof complexity

This page was built for publication: Regular resolution lower bounds for the weak pigeonhole principle