文章基本信息

标题：Strongly Exponential Lower Bounds for Monotone Computation
本地全文：下载
作者：Toniann Pitassi ; Robert Robere
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2016
卷号：2016
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：For a universal constant 0"> 0 , we prove size lower bounds of 2 N for computing an explicit monotone function in NP in the following models of computation: monotone formulas, monotone switching networks, monotone span programs, and monotone comparator circuits, where N is the number of variables of the underlying function. Our lower bounds improve on the best previous bounds in each of these models, and are the best possible for any function up to the constant factor . Moreover, we give one unified proof that is short and fairly elementary.
关键词：Comparator Circuits ; formula ; lower bounds ; monotone circuit complexity ; span program ; switching networks