首页    期刊浏览 2024年12月02日 星期一
登录注册

文章基本信息

  • 标题:Heuristic time hierarchies via hierarchies for sampling distributions
  • 本地全文:下载
  • 作者:Dmitry Itsykson ; Alexander Knop ; Dmitry Sokolov
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We give a new simple proof of the time hierarchy theorem for heuristic BPP originally proved by Fortnow and Santhanam [FS04] and then simplified and improved by Pervyshev [P07]. In the proof we use a hierarchy theorem for sampling distributions recently proved by Watson [W13]. As a byproduct we get that P is not included in BPTime[ n k ] if one way functions exist. As far as we know this statement was not known before. We also show that our technique may be extended for time hierarchies in some other heuristic classes.

  • 关键词:BPP ; heuristic algorithms ; Sampling Distributions ; Semantic Classes ; time hierarchy
国家哲学社会科学文献中心版权所有