首页    期刊浏览 2024年10月04日 星期五
登录注册

文章基本信息

  • 标题:Proving that prBPP=prP is as hard as "almost" proving that P \ne NP
  • 本地全文:下载
  • 作者:Roei Tell
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2018
  • 卷号:2018
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We show that any proof that promise - = p romise - necessitates proving circuit lower bounds that almost yield that = . More accurately, we show that if promise - = p romise - , then for essentially any super-constant function f ( n ) = (1) it holds that NTIM E [ n f ( n ) ] pol y . The conclusion of the foregoing conditional statement cannot be improved (to conclude that pol y ) without \emph{unconditionally} proving that = .

    This paper is a direct follow-up to the very recent breakthrough of Murray and Williams (ECCC, 2017), in which they proved a new ``easy witness lemma'' for NTIM E [ o ( 2 n )] . Following their approach, we apply the new lemma within the celebrated proof strategy of Williams (SICOMP, 2013), and derive our result by using a parameter setting that is different than the ones they considered.

  • 关键词:circuit lower bounds ; derandomization
国家哲学社会科学文献中心版权所有