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 '14 at 0:15
  • $\begingroup$ The title reminds PAC = "probably approximately correct" which Josh mentioned in his comment on cstheory. $\endgroup$ – Kaveh Sep 11 '14 at 18:27

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.