ALMOST-R: characterizations using different concepts of randomness
Abstract
We study here the classes of the form ALMOST-R, for R a reducibility. This includes among other the classes BPP, P and PH. We give a characterization of this classes in terms of reducibility to n-random languages, a subclass of algorithmically random languages. We also give a characterization of classes of the form ALMOST-R in terms of resource bounded measure, for R reducibility of a restricted kind.
Full text
ALMOST-'R: Characterizations using Different Concepts of Randomness Ronald V. Book Department of Mathematics U ni versi ty of California Santa Barbara, CA 93106 USA ( e-mail: bo[email protected]) and Elvira Mayordomo* Departament L. S. I. Universitat Politecnica de Catalunya Pau Gargallo 5 08028 Barcelona, Spain ( e-mail: mayordom[email protected]) Abstract We study here the classes of the form ALMOST-R, for R a reducibility. This includes among other the classes BPP, P and PH. We give a characterization of this classes in terms of reducibility to n-random languages, a subclass of algorithmically random languages. We also give a characterization of classes of the form ALMOST-R in terms of resource bounded measure, for R reducibility of a restricted kind. •supported by a Spanish Government Grant FPI PN90. This work was done while visiting the University of California, supported by this grant. 55