Skip to main content

Research Repository

Advanced Search

Tree resolution proofs of the weak pigeon-hole principle

Dantchev, Stefan; Riis, Søren

Tree resolution proofs of the weak pigeon-hole principle Thumbnail


Authors

Søren Riis



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). Tree resolution proofs of the weak pigeon-hole principle. In 16th Annual IEEE Conference on Computational Complexity, 18-21 June 2001, Chicago, Illinois ; proceedings (69-77). https://doi.org/10.1109/ccc.2001.933873

Conference Name 16th Annual IEEE Conference on Computational Complexity
Conference Location Chicago, Ill
Start Date Jun 18, 2001
End Date Jun 21, 2001
Publication Date 2001-06
Deposit Date Jul 9, 2007
Publicly Available Date Mar 29, 2024
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
Additional Information Conference dates: 18-21 Jun 2001.

Files

Published Conference Proceeding (620 Kb)
PDF

Copyright Statement
© 2001 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.





You might also like



Downloadable Citations