On the robustness of ALMOST-$\mathcal {R}$
Ronald V. Book, Elvira Mayordomo · RAIRO - Theoretical Informatics and Applications · 1996
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 charaderization of these classes in terms of réductions to n-random languages, a subclass of algorithmically random languages.We also discuss the possibility of char acte rizing the classes ALMOST-R in terms of resource bounded measure.