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.

Improve this question
$\endgroup$
3
  • $\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, 2019 at 13:09
  • $\begingroup$ @YOUSEFY is this under some assumption about exist of strong enough pseudo random number generators? $\endgroup$
    – Elle Najt
    Nov 10, 2019 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, 2019 at 12:38

0

Reset to default

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.