Relativized Separations of Worst-Case and Average-Case Complexities for NP
Relativized Separations of Worst-Case and Average-Case Complexities for NP
复制标题
NP 最坏情况和平均情况复杂性的相对分离
DOI：
10.1109/ccc.2011.34
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
R. Impagliazzo
中科院分区：
文献类型：
--
作者：
R. Impagliazzo
复杂性问题的非相对化可以被解释为表明这些问题不能通过“黑箱”技术来解决。我们用相对化的方法证明了AvgP中包含的NP = DistNP并不意味着NP =RP。更准确地说，我们给出了一个预言相对于其假设成立，但结论失败。此外，相对于我们的预言，在NP和CoNP的交集中存在需要指数电路复杂度的问题，我们也给出了另一个版本，其中DistNP包含在Avgp中是真的，但在多项式层次的第二层中的问题在均匀分布上是困难的。
Non-relativization of complexity issues can beinterpreted as showing that these issues cannot be resolvedby "black-box" techniques. We show that the assumptionDistNP is contained in AvgP does not imply that NP =RP byrelativizing techniques. More precisely, we give an oraclerelative to which the assumption holds but the conclusionfails. Moreover, relative to our oracle, there are problems inthe intersection of NP and CoNP that require exponential circuit complexity.We also give an alternate version where DistNP is contained in AvgPis true, but a problem in the second level of the polynomialhierarchy is hard on the uniform distribution.