期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Recently, Raz established exponential lower bounds on the size of resolution proofs of the weak pigeonhole principle. We give another proof of this result which leads to better numerical bounds. Specifically, we show that every resolution proof of PH P n m must have size exp \of ( n log m ) 1 2 which implies an exp \of ( n 1 3 ) bound when the number of pigeons m is arbitrary. As a step toward extending this bound to the {\em functional} version of PH P n m (in which one pigeon may not split between several holes), we introduce one intermediate version (in the form of a PH P -oriented calculus) which, roughly speaking, allows arbitrary ``monotone reasoning'' about the location of an individual pigeon. For this version we prove an exp \of ( n log 2 m ) 1 2 lower bound ( exp \of ( n 1 4 ) for arbitrary m ).
( n 
