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

文章基本信息

  • 标题:Improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances''
  • 本地全文:下载
  • 作者:Nikolay Vereshchagin
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2011
  • 卷号:2011
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Assume that NP is not included in BPP. Gutfreund, Shaltiel, and Ta-Shma in [Computational Complexity 16(4):412-441 (2007)] have proved that for every randomized polynomial time decision algorithm D for SAT there is a polynomial time samplable distribution such that D errs with probability at least 1/6-epsilonon a random formula chosen with respect to that distribution. In this paper, we show how to increase the error probability to 1/3-epsilon.

  • 关键词:average-case complexity; pseudo classes; samplable distribution; worst-case to average-case reductions
国家哲学社会科学文献中心版权所有