首页    期刊浏览 2025年02月27日 星期四
登录注册

文章基本信息

  • 标题:An Approach to characterize the Regular Languages in TC0 with Linear Wires
  • 本地全文:下载
  • 作者:Christoph Behle ; Andreas Krebs ; Stephanie Reifferscheid
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2009
  • 卷号:2009
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We consider the regular languages recognized by weighted threshold circuits with a linear number of wires.We present a simple proof to show that parity cannot be computed by such circuits.Our proofs are based on an explicit construction to restrict the input of the circuit such that the value computed by the circuit are constant.The result is also a corollary of [IPS93] where a different proof method based on randomized restrictions.

  • 关键词:circuit complexity; Combinatorics; linear wires; regular languages; TC0
国家哲学社会科学文献中心版权所有