On Properties of Random Reductions
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
Abstract
Randomness is widely accepted as a powerful computational resource because the most elegant and efficient solutions to several computational problems are randomized. A recurrent theme in the theory of randomized computation is the notion of a random reduction. Random reductions are similar to many-one (