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.
展开▼
机译：我们证明，信鸽原理的{ em功能}版本FPH P n m的每个分辨率证明（其中一只信鸽可能不会在多个孔之间分裂）必须具有 n（log m）2的大小exp。这意味着当鸽子数m为任意时，exp of（n 1 3）界。
展开▼
