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

文章基本信息

  • 标题:Progress on Polynomial Identity Testing
  • 本地全文:下载
  • 作者:Nitin Saxena
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2009
  • 卷号:2009
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Polynomial identity testing (PIT) is the problem of checking whether a givenarithmetic circuit is the zero circuit. PIT ranks as one of the most important open problems in the intersection of algebra and computational complexity. In the lastfew years, there has been an impressive progress on this problem but a complete solution might take a while. In this article we give a soft survey exhibiting the ideas that have been useful.

  • 关键词:circuits; depth-3; depth-4; identity testing; lower bounds
国家哲学社会科学文献中心版权所有