文章基本信息

标题：Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems
本地全文：下载
作者：Akinori Kawachi ; Osamu Watanabe
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Impagliazzo and Levin demonstrated [IL90] that the average-case hardness of any NP-search problem under any P-samplable distribution implies that of another NP-search problem under the uniform distribution. For this they developed a way to define a reduction from an NP-search problem F with ``mild hardness'' under any P-samplable distribution H; more specifically, F is a problem with positive hard instances with probability 1/poly(n) under H. In this paper we show a similar reduction for an NP-search problem F with ``strong hardness'', that is, F with positive hard instances with probability 1-1/poly(n) under H in its positive domain (i.e., the set of positive instances). Our reduction defines from this pair of F and H, some NP-search problem G with a similar hardness under the uniform distribution U; more precisely, (i) G has positive hard instances with probability 1-1/poly(n) under U in its positive domain, and (ii) the positive domain itself occupies 1/poly(n) of {0,1}^n.
关键词：average-case complexity , distributional NP search problems , polynomial-time samplable distributions , reduction