On Properties of Random Reductions

Other Titles


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 (mP) reductions except for the fact that they are carried out by probablistic transducers which may make errors with small probability. Such reductions are used explicitly in many basic results in complexity theory and implicitly in several randomized algorithms. This thesis investigates the properties of random reductions as a tool towards understanding the power and limitations of randomness. We first prove some startling results which indicate that random reductions can be quite successful in reducing harder problems to simpler ones. We then propose the thesis that in many situations there is a sharp {\em probability threshold} which governs just how successful random reductions can be in this regard. As evidence, we prove that for several complexity classes C, under standard assumptions, there exist corresponding {\em probability thresholds/} CT, such that random reductions with success probability below CT can reduce the hardest languages in C to simpler ones but reductions with success probability above CT cannot do so. Based on these thresholds, we then propose a meaningful definition of completeness under random reductions which resolves several anomalies caused by the traditional definitions which did not place much emphasis on the success probability. The results described above depend on standard but unproven complexity-theoretic assumptions. In order to show that such behavior is inherent to random reductions and not an artifact introduced by these assumptions, we also prove that it is present in very high complexity classes {\em without any assumptions}. In this thesis we also examine other basic aspects of random reducibility. We prove several {\em absolute} separation results between the notions of completeness under various polynomial-time random reductions with different success probabilities and between various random reductions and deterministic polynomial-time reductions. In addition, we also prove new results on the consequences of having random reductions from NP-complete sets to sparse sets.

Journal / Series

Volume & Issue



Date Issued



Cornell University


computer science; technical report


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record