首页    期刊浏览 2024年07月09日 星期二
登录注册

文章基本信息

  • 标题:Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP
  • 本地全文:下载
  • 作者:Bin Fu
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2013
  • 卷号:2013
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We show thatderandomizing polynomial identity testing over an arbitrary finitefield implies that NEXP does not have polynomial size booleancircuits. In other words, for any finite field F(q) of size q,PITqNSUBEXPNEXPPpoly , wherePITq is the polynomial identity testing problem over F(q), andNSUBEXP is the nondeterministic subexpoential time class oflanguages. Our result is in contract to Kabanets and Impagliazzo'sexisting theorem that derandomizing the polynomial identity testingin the integer ring Z implies that NEXP does have polynomialsize boolean circuits or permanent over Z does not have polynomialsize arithmetic circuits.

国家哲学社会科学文献中心版权所有