We prove a quasi-polynomial lower bound on the size of bounded-depth Frege proofs of the pigeonhole principle PH P n m where m = ( 1 + 1 polylog n ) n . This lower bound qualitatively matches the known quasi-polynomial-size bounded-depth Frege proofs for these principles. Our technique, which uses a switching lemma argument like other lower bounds for bounded-depth Frege proofs, is novel in that the tautology to which this switching lemma is applied remains random throughout the argument.
展开▼
机译：我们证明了信鸽原理PH P n m的有界深度弗雷格证明的大小的拟多项式下界，其中m =（1 +1 polylog n）n。对于这些原理，该下限在质量上与已知的拟多项式大小的有界深度Frege证明相匹配。我们的技术将切换引理参数与其他下限一样用于边界深度Frege证明，它是新颖的，因为在整个引数中，应用此切换引理的重言式仍然是随机的。
展开▼
