Dr Stefan Dantchev s.s.dantchev@durham.ac.uk
Assistant Professor
Tree resolution proofs of the weak pigeon-hole principle
Dantchev, Stefan; Riis, Søren
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
Combinatorial Axiomatisation of Edge-weighted PageRank
(2016)
Journal Article
Relativization makes contradictions harder for Resolution
(2013)
Journal Article
Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
(2012)
Journal Article
Cutting Planes and the Parameter Cutwidth
(2012)
Journal Article
Parameterized Proof Complexity
(2011)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search