On worst-case to average-case reductions for NP problems
On worst-case to average-case reductions for NP problems
复制标题
关于 NP 问题的最坏情况到平均情况的减少
DOI：
10.1109/sfcs.2003.1238205
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
L. Trevisan
中科院分区：
文献类型：
--
作者：
Andrej Bogdanov;L. Trevisan
我们证明，如果 NP 完全问题对于可采样的分布具有非自适应自校正器，则 coNP 包含在 AM/poly 中，并且多项式层次结构崩溃到第三级。 Feigenbaum 和 Fortnow 在更强的假设下得出了相同的结论，即 NP 完全问题具有非自适应随机自约简。我们的结果表明，不可能（使用非自适应约简）将 NP 问题的平均情况硬度或单向函数的安全性建立在 NP 完全问题的最坏情况复杂性的基础上（除非多项式层次结构崩溃）。
We show that if an NP-complete problem has a non-adaptive self-corrector with respect to a distribution that can be sampled then coNP is contained in AM/poly and the polynomial hierarchy collapses to the third level. Feigenbaum and Fortnow show the same conclusion under the stronger assumption that an NP-complete problem has a non-adaptive random self-reduction. Our result shows it is impossible (using non-adaptive reductions) to base the average-case hardness of a problem in NP or the security of a one-way function on the worst-case complexity of an NP-complete problem (unless the polynomial hierarchy collapses).