What's the name of a complexity class of optimization problems that have "bounded error probabilistic approximation algorithms"? Bounded error probabilistic version of APX (as BPP is bounded error probabilistic version of P), or approximation version of BPP (as APX is approximation version of P).

  • 3
    $\begingroup$ This question was reposted and answered on cstheory.se: cstheory.stackexchange.com/questions/20599/… $\endgroup$
    – mdxn
    Aug 29, 2014 at 0:15
  • $\begingroup$ The title reminds PAC = "probably approximately correct" which Josh mentioned in his comment on cstheory. $\endgroup$
    – Kaveh
    Sep 11, 2014 at 18:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.