Do there exist polynomial time algorithms that admit Probably Approximately Correct (PAC) bounds for APX-Hard problems? That is, does there exist a problem $P$ that is APX-Hard, such that for every $\epsilon, \delta > 0$, we have an algorithm that runs in polynomial time in $n$ that gives a $1 + \epsilon$ approximation to it with probability $1 - \delta$. Note that the randomness is not dependent on the instance of $P$ given, but some randomness of the algorithm.

  • 2
    $\begingroup$ Aren't you just asking if an APX-hard problem admits a PRAS ? I don't think PAC has anything to do with it since the randomness is not over the input. $\endgroup$ Mar 28, 2014 at 18:18
  • 3
    $\begingroup$ Is it well-defined to take such a problem $P$ and ask about PAC algorithms for it? You need to define a concept class and the set of possible examples, etc. Or maybe I am not familiar enough with PAC learning and there is some (obvious) assumed choice...? $\endgroup$
    – usul
    Mar 28, 2014 at 18:22
  • 2
    $\begingroup$ The way you defined the guarantees, they would imply NP is in BPP. $\endgroup$ Mar 28, 2014 at 18:35
  • 2
    $\begingroup$ @SureshVenkat maybe I am missing something, but doesn't APX hardness mean that there is a polytime reduction from an NP-hard problem to approximating $P$ better than $1+\epsilon_0$ for some fixed $\epsilon_0$? So if you can approximate $P$ to within $1 + 0.5\epsilon_0$ with probability $2/3$, doesn't this and the reduction give a BPP algorithm for NP? It definitely seems to hold for gap problems. $\endgroup$ Mar 29, 2014 at 15:44
  • 1
    $\begingroup$ @SashoNikolov ah I see what you mean. Good point. I think you should convert your comment above (and the explanation above) into an answer. $\endgroup$ Mar 29, 2014 at 20:35

1 Answer 1


If you had an approximation algorithm for an APX-hard problem which for any $\epsilon, \delta >0$ runs in polynomial time and approximates the problem within a factor of $1+\epsilon$ with probability $1-\delta$, then $\mathsf{NP} \subseteq \mathsf{BPP}$.

The reasoning is very similar to Chandra's answer to another question. APX-hardness for a problem $P$ implies that there is a PTAS reduction from instances of MaxSAT to instances of $P$: for every $\epsilon$, approximating Max3SAT to within a factor of $1+\epsilon$ is polynomial-time reducible to approximating $P$ to within a factor of $1 + c(\epsilon)$. By the PCP theorem, there is a constant $\epsilon_0$ such that the promise problem of distinguishing between satisfiable 3SAT instances and instances where at most a $1-\epsilon_0$ fraction of the constraints can be satisfied is NP-hard (in fact $\epsilon_0$ can be taken arbitrarily close to $1/8$, which is tight). Call this NP-hard promise problem $\text{Gap3SAT}(1, 1-\epsilon_0)$. The PTAS reduction from Max3SAT to $P$ with small enough $\epsilon$ (i.e. $\epsilon < \frac{\epsilon_0}{1-\epsilon_0}$), together with the algorithm with "PAC guarantees", give a BPP algorithm for $\text{Gap3SAT}(1, 1-\epsilon_0)$, which implies a BPP algorithm for any problem in NP.


Your Answer

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

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