文章基本信息

标题：Interpolation by a game
本地全文：下载
作者：Jan Krajicek
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We introduce a notion of a "real game" (a generalization of the Karchmer - Wigderson game), and "real communication complexity", and relate them to the size of monotone real formulas and circuits. We give an exponential lower bound for tree-like monotone protocols of small real communication complexity solving the monotone communication complexity problem associated with the bipartite perfect matching problem. This work is motivated by a research in interpolation theorems for propositional logic. Our main objective is to extend the communication complexity approach of our earlier papers to a wider class of proof systems. In this direction we obtain an effective (monotone) interpolation in a form of a protocol of small real communication complexity. Together with the above mentioned lower bound for tree - like protocols this yields as a corollary a lower bound on the number of steps for particular semantic derivations of Hall's theorem (these include tree - like cutting planes proofs for which an exponential lower bound was demonstrated by Impagliazzo et. al.).
关键词：Communication complexity, effective interpolation theorems, lower bounds, propositional logic