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

文章基本信息

  • 标题:Collapsing Exact Arithmetic Hierarchies
  • 本地全文:下载
  • 作者:Nikhil Balaji ; Samir Datta
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2013
  • 卷号:2013
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We provide a uniform framework for proving the collapse of the hierarchy, NC1()for an exact arithmetic class of polynomial degree. These hierarchies collapses all the way down to the third level of the AC0-hierarchy, AC30(). Our main collapsing exhibits are the classes C=NC1C=LC=SAC1C=P NC1(C=L) and NC1(C=P) are already known to collapse \cite{ABO,Ogihara95,Ogiwara94}.

    We reiterate that our contribution is a framework that works for \emph{all} these hierarchies.Our proof generalizes a proof from \cite{DMRTV} where it is used to prove thecollapse of the AC0(C=NC1) hierarchy. It is essentially based on a polynomialdegree characterization of each of the base classes.

  • 关键词:arithmetic circuits; counting classes; hierarchies
国家哲学社会科学文献中心版权所有