11
$\begingroup$

I am looking for a complexity class that relates to APX as BPP relates to P. I have already asked the same question here, 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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Jan 16, 2014 at 3:11
  • 1
    $\begingroup$ 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... $\endgroup$
    – Joshua Grochow
    Jan 16, 2014 at 5:51
  • 3
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Jan 16, 2014 at 14:28

1 Answer 1

Reset to default
1
$\begingroup$

For any given objective function, let BotL (best-of-the-list) be the algorithm that evaluates the objective function on a set of inputs and returns an input from that list that had maximal output (from among those inputs), with ties broken arbitrarily. $\:$ Since APX only includes problems
who's objective function can be computed in deterministic polynomial time, BotL can be implemented deterministically in polynomial time. $\:$ Furthermore, the value returned by BotL
is at least as good as any of inputs in the least that BotL was evaluated on. $\:$ In particular,
if any of the inputs in that list is good-enough then BotL's output will be good-enough.
Therefore running BotL on the outputs of a sufficiently large number of independent executions of a base algorithm can amplify the success probability from 1/poly to 1-(1/(2^poly)).

As consequence of the preceding paragraph, the precise
confidence level essentially does not affect the resulting class.
(This situation is highly analogous to RP.)

I was not able to find anything about that on the complexity zoo, although there
might have been talks on it given at the workshop referred to in this paper.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ OP is asking for the name of the class of problems that have a randomized constant factor approximation algorithms. You are saying (I think) that the probability of success for such algorithms can be amplified. I am failing to see how this answers the question? $\endgroup$
    – Sasho Nikolov
    Jan 16, 2014 at 2:45
  • $\begingroup$ I don't see that question in the OP. $\:$ Michael is asking if the class has "been extensively studied". $\:$ Admittedly, I didn't have much to say about that, but I did (at least try to) address a misunderstanding about what such a class would be. $\;\;\;$ $\endgroup$
    – user6973
    Jan 16, 2014 at 2:55
  • $\begingroup$ There is no such misunderstanding in the question. $\endgroup$
    – Sasho Nikolov
    Jan 16, 2014 at 3:29
  • $\begingroup$ Right. $\:$ The misunderstanding is in the "A possible candidate of such class would be ... probabilistically computable approximations." paragraph, which is in the post but not the question. $\;\;\;$ $\endgroup$
    – user6973
    Jan 16, 2014 at 3:35
  • 1
    $\begingroup$ With the clarifications, it's still my opinion that your answer is not correcting a misunderstanding in the OP, but just gives an arbitrary fact about randomized approximations. $\endgroup$
    – Sasho Nikolov
    Jan 16, 2014 at 14:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.