ON THE ROBUSTNESS OF ALMOST-R

摘要

We study the classes of the form ALMOST-R, for R a reducibility. This includes, among others, the classes BPP, P and PH. We give a characterization of these classes in terms of reductions to n-random languages, a subclass of algorithmically random languages. We also discuss the possibility of characterizing the classes ALMOST-R in terms of resource bounded measure.