1
$\begingroup$

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.

|cite|improve this question|||||
$\endgroup$
  • $\begingroup$ 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] $\endgroup$ – YOUSEFY Nov 10 '19 at 13:09
  • $\begingroup$ @YOUSEFY is this under some assumption about exist of strong enough pseudo random number generators? $\endgroup$ – Lorenzo Najt Nov 10 '19 at 14:17
  • $\begingroup$ 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. $\endgroup$ – YOUSEFY Nov 12 '19 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.