期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that every resolution proof of the {\em functional} version FPH P n m of the pigeonhole principle (in which one pigeon may not split between several holes) must have size exp \of \of n ( log m ) 2 . This implies an exp \of ( n 1 3 ) bound when the number of pigeons m is arbitrary.
\of n ( log m ) 2 . This implies an exp \of 
