RANDOMIZING REDUCTIONS OF SEARCH PROBLEMS

This paper closes a gap in the foundations of the theory of average-ca se complexity. First, it clarifies the notion of a feasible solution f or a search problem and proves its robustness. Second, it gives a gene ral and usable notion of many-one randomizing reductions of search pro blems and proves that it has desirable properties. All reductions of s earch problems to search problems in the literature on average-case co mplexity can be viewed as such many-one randomizing reductions, includ ing those reductions in the literature that use iterations and therefo re do not look many-one. As an illustration, this paper presents a car eful proof of a theorem of Impagliazzo and Levin in the framework of t he present work.