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).
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ This question was reposted and answered on cstheory.se: cstheory.stackexchange.com/questions/20599/… $\endgroup$– mdxnCommented Aug 29, 2014 at 0:15
-
$\begingroup$ The title reminds PAC = "probably approximately correct" which Josh mentioned in his comment on cstheory. $\endgroup$– KavehCommented Sep 11, 2014 at 18:27
Add a comment
|