Tree resolution proofs of the weak pigeon-hole principle
(2001)
Presentation / Conference Contribution
Dantchev, S., & Riis, S. (2001, June). Tree resolution proofs of the weak pigeon-hole principle. Presented at 16th Annual IEEE Conference on Computational Complexity, Chicago, Ill
We prove that any optimal tree resolution proof of PHPn m is of size 2&thetas;(n log n), independently from m, even if it is infinity. So far, only a 2Ω(n) lower bound has been known in the general case. We also show that any, not necessarily optimal... Read More about Tree resolution proofs of the weak pigeon-hole principle.