Random Polynomial Time Computable Functions
Mitsunori Ogiwara, Kenneth W. Regan · 2000
Many randomized algorithms M in the literature have the following features: M may produce different valid outputs for different random strings, may output erroneous values, and/or may fail to give any output at all. This paper formalizes and studies these features, and compares the probabilistic function classes thus defined to language classes such as BPP, RP, and ZPP. The two main problems we study are whether the distribution of outputs can be skewed in favor of one valid value, and whether the probability that M behaves correctly can be amplified. We show that if a certain symmetry between two values in fully-polynomial randomized approximation schemes can be broken, then the answer to the former is yes, and we prove many cases in which the answer to the latter is no. Note: This paper was originally submitted to the Complexity 1994 conference, before the first author adopted “Ogihara ” as his Roman spelling. Our e-mails are now