• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Processing Letters >Proving that prBPP = prP is as hard as proving that 'almost NP' is not contained in P/poly
【24h】

Proving that prBPP = prP is as hard as proving that 'almost NP' is not contained in P/poly

机译：证明prBPP = prP与证明P / poly中不包含“几乎NP”一样困难

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

What circuit lower bounds are necessary in order to prove that promise-BPP=promise-P? We show that the recent breakthrough result of Murray and Williams (STOC 2018) can be used to show a dramatic strengthening of the previously-known answer to this question. Specifically, we show that if promise-BPP = promise-P, then NTIME[n(f(n))] not subset of P/poly, for essentially any f (n) = omega(1).We also prove a technical strengthening of this result. Specifically, we show that if promise-BPP=promise-P, then for essentially any s : N > N it holds that NT IME[s0(1) o sole] not subset of SIZE[s]. Moreover, we show that size-s circuits fail to compute the "hard" function in any interval of length poly(s(poly(n))). The proof of this result uses tools of Murray and Williams, but relies on a different proof strategy. (Their proof strategy yields three compositions of s instead of two, and does not yield the guarantee of failure in any small interval.) (C) 2019 Elsevier B.V. All rights reserved.
机译：为了证明promise-BPP = promise-P，什么电路下限是必需的？我们表明，Murray和Williams（STOC 2018）的最新突破性结果可以用来显示对这个问题的先前已知答案的显着增强。具体来说，我们表明，如果对于任何f（n）= omega（1），基本上，如果promise-BPP = promise-P，则NTIME [n（f（n））]不是P / poly的子集。加强这一结果。具体来说，我们表明，如果promise-BPP = promise-P，则对于任何s：N> N，它都认为NT IME [s0（1）o sole]不是SIZE [s]的子集。此外，我们表明，在任何长度的poly（s（poly（n）））区间中，size-s电路都无法计算“硬”函数。该结果的证明使用了Murray和Williams的工具，但是依赖于不同的证明策略。 （他们的证明策略产生了s的三个组成而不是两个组成，并且在任何很小的时间间隔内都无法保证失败。）（C）2019 Elsevier B.V.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号