# Randomized version of the class $APX$?

Is there a class which is to APX what BPP is to P?

I'm looking for a definition that is like the following:

"For $$r > 0$$, an $$r$$-RPCA (randomized polynomial-time constant-factor approximation) algorithm for a function problem $$T : \Sigma^* \to \mathbb{N}$$ is a probabilistic Turing machine $$A$$ with the following property: $$A$$ runs in time $$poly(|x|)$$ and has $$\mathbb{P}( r^{-1} T(x) \leq A(x) \leq r T(x)) \geq 2/3$$."

I think that either a class like this exists and has a standard name, or there is something wrong with it. I'm looking for a similar definition with which to cleanly state a result.

• Good question. I haven't seen any class of randomized version of APX. But, as far as I know, all constant-factor randomized approximation algorithm can be always derandomized with at most polynomial of the size of the input. Thus, I think but I'm not sure, people did not have this class; because they always can derandmoize it. [Note that we have a randomized version of PTAS, see definition 11.2 in Motwani and Raghavan's textbook, p.309] Nov 10 '19 at 13:09
• @YOUSEFY is this under some assumption about exist of strong enough pseudo random number generators? Nov 10 '19 at 14:17
• Sorry for not reply in time. Well, this is another good question if there is some assumption like strong pseudo random generators. My answer is: I don't know. Nov 12 '19 at 12:38