ECCC-Report TR09-023https://eccc.weizmann.ac.il/report/2009/023Comments and Revisions published for TR09-023en-usSat, 21 Mar 2009 10:19:06 +0200
Paper TR09-023
| Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems |
Akinori Kawachi,
Osamu Watanabe
https://eccc.weizmann.ac.il/report/2009/023Impagliazzo 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.
Sat, 21 Mar 2009 10:19:06 +0200https://eccc.weizmann.ac.il/report/2009/023