Worst-Case to Average-Case Reductions Revisited
Worst-Case to Average-Case Reductions Revisited
复制标题
重新审视最坏情况到平均情况的减少
DOI：
10.1007/978-3-540-74208-1_41
复制
发表时间：
2007
影响因子：
1.4
通讯作者：
A. Ta
中科院分区：
文献类型：
--
作者：
Dan Gutfreund;A. Ta
计算复杂性的一个基本目标（和密码学的基础）是为某些多项式函数f找到一个多项式时间可抽样分布（例如，均匀分布）和一种NTIME（f(n)）的语言，使得该语言相对于该分布的平均困难，假设NP是最坏情况困难(即NP i¾？P，或${\rm NP} \非\subseteq {\rm BPP}$)。目前，即使我们将语言放宽到不确定的次指数时间，也没有这样的结果。已经有很多研究试图解释我们无法证明这种最坏情况/平均情况的联系[FF93，Vio03,BT03,AGGM06]。这项研究的底线本质上是（在合理的假设下）非自适应图灵约简不能证明这样的结果。
A fundamental goal of computational complexity (and foundations of cryptography) is to find a polynomial-time samplable distribution (e.g., the uniform distribution) and a language in NTIME(f(n)) for some polynomial function f, such that the language is hard on the average with respect to this distribution, given that NP is worst-case hard (i.e. NP i¾? P, or ${\rm NP} \not \subseteq {\rm BPP}$). Currently, no such result is known even if we relax the language to be in nondeterministic sub-exponential time. There has been a long line of research trying to explain our failure in proving such worst-case/average-case connections [FF93,Vio03,BT03,AGGM06]. The bottom line of this research is essentially that (under plausible assumptions) non-adaptive Turing reductions cannot prove such results.
In this paper we revisit the problem. Our first observation is that the above mentioned negative arguments extend to a non-standard notion of average-case complexity, in which the distribution on the inputs with respect to which we measure the average-case complexity of the language, is only samplable in super-polynomial time. The significance of this result stems from the fact that in this non-standard setting,[GSTS05] did show a worst-case/average-case connection. In other words, their techniques give a way to bypass the impossibility arguments. By taking a closer look at the proof of [GSTS05], we discover that the worst-case/average-case connection is proven by a reduction that "almost" falls under the category ruled out by the negative result. This gives rise to an intriguing new notion of (almost black-box) reductions.
After extending the negative results to the non-standard average-case setting of [GSTS05], we ask whether their positive result can be extended to the standard setting, to prove some new worst-case/average-case connections. While we can not do that unconditionally, we are able to show that under a mild derandomization assumption, the worst-case hardness of NP implies the average-case hardness of NTIME(f(n)) (under the uniform distribution) where fis computable in quasi-polynomial time.