Rohatgi, Pankaj2007-04-232007-04-231993-09http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1386https://hdl.handle.net/1813/6160Randomness 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 ($\leq^{P}_{m}$) 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 ${\cal C}$, under standard assumptions, there exist corresponding {\em probability thresholds\/} ${\cal C}_T$, such that random reductions with success probability below ${\cal C}_T$ can reduce the hardest languages in ${\cal C}$ to simpler ones but reductions with success probability above ${\cal C}_T$ 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.7868687 bytes2104249 bytesapplication/pdfapplication/postscripten-UScomputer sciencetechnical reporttechnical report