首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Lower Bounds for (Non-monotone) Comparator Circuits
  • 本地全文:下载
  • 作者:Anna Gal ; Robert Robere
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-15
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Comparator circuits are a natural circuit model for studying the concept of bounded fan-out computations, which intuitively corresponds to whether or not a computational model can make "copies" of intermediate computational steps. Comparator circuits are believed to be weaker than general Boolean circuits, but they can simulate Branching Programs and Boolean formulas. In this paper we prove the first superlinear lower bounds in the general (non-monotone) version of this model for an explicitly defined function. More precisely, we prove that the n -bit Element Distinctness function requires (( n log n ) 3 2 ) size comparator circuits.

  • 关键词:circuit complexity ; Comparator Circuits ; lower bounds ; Nechiporuk method
国家哲学社会科学文献中心版权所有