Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.


Durham Research Online
You are in:

Tree resolution proofs of the weak pigeon-hole principle.

Dantchev, S.. and 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. New York: IEEE, pp. 69-77.

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.

Item Type:Book chapter
Full text:PDF - Published Version (606Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1109/CCC.2001.933873
Publisher 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.
Record Created:09 Jul 2007
Last Modified:01 Nov 2010 15:27

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library