<p>I am looking for a complexity class that relates to APX as BPP relates to P. I have already asked the same question <a href="https://cs.stackexchange.com/questions/19583/almost-always-almost-right">here</a>, but perhaps TCS would be a more fruitful location for answers.</p>

<p>The reason for the question is that in practical problems one often needs to find approximate answers (thus APX) with sufficiently high confidence (thus BPP), which would make the class of problems with bounded probabilistic approximation algorithms potentially a useful model of what's computable in practice.</p>

<p>A possible candidate of such class would be $APX^{BPP}$: problems that admit approximated solutions with bounded probabilistic subroutines; however, I'm not confident that such class would be the appropriate setting for the class probabilistically computable approximations.</p>

<p>Both BPP and APX have been extensively studied. Is that the case for $APX^{BPP}$, or whichever class would be the best to capture the above problems?</p>

CC BY-SA 3.0
2014-01-16T03:11:17.300Z
BPP and P are decision problem classes. Maybe you should first ask what is the function/search class corresponding to BPP before moving to approximation, I think if we have the function/search class then the definition of its approximation version shouldn't be difficult.
Kaveh
CC BY-SA 3.0
2014-01-16T05:51:54.667Z
I think what you're looking for is the optimization version of PAC (Probably Approximately Correct) learning. Whereas the theory of PAC learning is specifically about (randomly, with high probably of correctness) learning *functions* to describe data, as in machine learning, you're asking about optimization problems. Still, maybe the PAC learning literature is a good place to start searching...
Joshua Grochow
CC BY-SA 3.0
2014-01-16T14:28:29.780Z
Rather than the oracle notation, what you are describing is closer to the BP operator. The BP operator is defined on complexity classes of decision problems. It should be easy to extend the definition to promise problems and define a promise problem version of your complexity class that way. Defining a version for optimization problems might be trickier.
Sasho Nikolov
<cc.complexity-theory><approximation-hardness>
Almost always almost right
Michael
# Almost always almost right

(Asked by: username_0 on 2014-01-16)

I am looking for a complexity class that relates to APX as BPP relates to P. I have already asked the same question [here](https://cs.stackexchange.com/questions/19583/almost-always-almost-right), but perhaps TCS would be a more fruitful location for answers.

The reason for the question is that in practical problems one often needs to find approximate answers (thus APX) with sufficiently high confidence (thus BPP), which would make the class of problems with bounded probabilistic approximation algorithms potentially a useful model of what's computable in practice.

A possible candidate of such class would be $APX^{BPP}$: problems that admit approximated solutions with bounded probabilistic subroutines; however, I'm not confident that such class would be the appropriate setting for the class probabilistically computable approximations.

Both BPP and APX have been extensively studied. Is that the case for $APX^{BPP}$, or whichever class would be the best to capture the above problems?

**Tags:** cc.complexity-theory, approximation-hardness
> **Comments:**
> **username_1**: BPP and P are decision problem classes. Maybe you should first ask what is the function/search class corresponding to BPP before moving to approximation, I think if we have the function/search class then the definition of its approximation version shouldn't be difficult.  
> **username_2**: I think what you're looking for is the optimization version of PAC (Probably Approximately Correct) learning. Whereas the theory of PAC learning is specifically about (randomly, with high probably of correctness) learning *functions* to describe data, as in machine learning, you're asking about optimization problems. Still, maybe the PAC learning literature is a good place to start searching...  
> **username_3**: Rather than the oracle notation, what you are describing is closer to the BP operator. The BP operator is defined on complexity classes of decision problems. It should be easy to extend the definition to promise problems and define a promise problem version of your complexity class that way. Defining a version for optimization problems might be trickier.  

---

## 0 answers

