Randomizing Reductions of Search Problems

This paper closes a gap in the foundations of the theory of average case complexity. First, we clarify the notion of a feasible solution for a search problem and prove its robustness. Second, we give a general and usable notion of many-one randomizing reductions of search problems and prove that it has desirable properties. All reductions of search problems to search problems in the literature on average case complexity can be viewed as suchmany-one randomizing reductions# this includes those reductions in the literature that use iterations and therefore do not look many-one. As an illustration, we present a careful proof in our framework of a theorem of Impagliazzo and Levin