Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems.
Akinori Kawachi, Osamu Watanabe · 2009
The theory of the average-case complexity has been studied extensively since 1970’s, and during late 80’s to early 90’s, several fundamental results have been shown (see an excellent survey [BT06b] for the background). Among such results, an average-case NP-completeness theorem shown by Impagliazzo and Levin [IL90] is one of the seminal results in the average-case com-