2026-04-17T02:53:19Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/972172025-07-17T07:18:01Zcom_2072_1033col_2072_452950

On the robustness of ALMOST-R Book, Ronald V. Mayordomo, Elvira Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica ALMOST-R Reducibility 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 this classes in terms of reductions to n-random languages, a subclass of algorithmically random languages. Also, we give a characterization of classes of the form ALMOST-R in terms of resource bounded measure, for R reductions of a restricted kind. Postprint (updated version) 1993-01-01 External research report LSI-93-27-R Open Access