On the Reduction Theory for Average-Case Complexity
- Yuri Gurevich
CSL'90, 4th Workshop on Computer Science Logic Springer Lecture Notes in Computer Science 533 |
A function from instances of one problem to instances of another problem is a reduction if together with any admissible algorithm for the second problem it gives an admissible algorithm for the first problem. This is an example of a descriptive definition of reductions. We simplify slightly Levin’s usable definition of deterministic average-case reductions and thus make it equivalent to the appropriate descriptive definition. Then we generalize this to randomized average-case reductions.