Tree resolution proofs of the weak pigeon-hole principle

Dantchev, Stefan; Riis, Søren

Abstract

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, regular tree resolution proof PHPn m is bounded by 2O(n log m). To the best of our knowledge, this is the first time the worst case proof complexity has been considered. Finally, we discuss possible connections of our result to Riis' (1999) complexity gap theorem for tree resolution.

Citation

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

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 16th Annual IEEE Conference on Computational Complexity
• Start Date: Jun 18, 2001
• End Date: Jun 21, 2001
• Publication Date: 2001-06
• Deposit Date: Jul 9, 2007
• Publicly Available Date: Nov 1, 2010
• Publisher: Institute of Electrical and Electronics Engineers
• Pages: 69-77
• Book Title: 16th Annual IEEE Conference on Computational Complexity, 18-21 June 2001, Chicago, Illinois ; proceedings.
• DOI: https://doi.org/10.1109/ccc.2001.933873
• Public URL: https://durham-repository.worktribe.com/output/1679679
• Additional Information: Conference dates: 18-21 Jun 2001.