文章基本信息

标题：Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-like Cutting Planes
本地全文：下载
作者：Jan Johannsen
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Using a notion of real communication complexity recently introduced by J. Krajicek, we prove a lower bound on the depth of monotone real circuits and the size of monotone real formulas for st-connectivity. This implies a super-polynomial speed-up of dag-like over tree-like Cutting Planes proofs.
关键词：Communication complexity, cutting planes, monotone circuit, propositionalproof system