Loading...
Please wait, while we are loading the content...
Similar Documents
Random Polynomial Time Computable Functions
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ogiwara, Mitsunori Regan, Kenneth W. |
| Copyright Year | 2000 |
| Abstract | Many randomized algorithms M in the literature have the following features: M may produce dierent valid outputs for dierent 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 dened 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 amplied. 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 rst author adopted \Ogihara" as his Roman spelling. Our e-mails are now |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cse.buffalo.edu/~regan/papers/pdf/BPMV2.pdf |
| Alternate Webpage(s) | http://www.cse.buffalo.edu/faculty/regan/papers/pdf/BPMV2.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
