文章基本信息

标题：Bounded-depth Frege lower bounds for weaker pigeonhole principles
本地全文：下载
作者：Josh Buresh-Oppenheim ; Paul Beame ; Toniann Pitassi 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2002
卷号：2002
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：Pigeonhole Principle , Proof Complexity