Randomizing Reductions of Search Problems

The journal version of an invited talk at FST&TCS’91, 11th Conference on Foundations of Software Technology and Theoretical Computer Science, New Delhi, India; see Springer Lecture Notes in Computer Science 560 (1991), 10-24.

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 such many-one randomizing reductions. This includes those reductions in the literature that use iterations and therefore do not look many-one.