文章基本信息

标题：Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games
本地全文：下载
作者：Eli Ben-Sasson ; Prahladh Harsha
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We present a simple proof of the bounded-depth Frege lower bounds of Pitassi et. al. and Krajicek et. al. for the pigeonhole principle. Our method uses the interpretation of proofs as two player games given by Pudlak and Buss. Our lower bound is conceptually simpler than previous ones, and relies on tools and intuition that are well-known in the context of computational complexity. This makes the lower bound of Pitassi et. al. and Krajicek et. al. accessible to the general computational complexity audience. We hope this new view will open new directions for research in proof complexity.
关键词：bounded depth circuits , bounded depth Frege , Proof Complexity , propositional proofs , switching lemma