<p>If you had an approximation algorithm for an APX-hard problem which for any $\epsilon, \delta &gt;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}$. </p>

<p>The reasoning is very similar to <a href="https://cstheory.stackexchange.com/a/21702/4896">Chandra's answer</a> to another question. APX-hardness for a problem $P$ implies that there is a <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node5.html" rel="nofollow noreferrer">PTAS reduction</a> 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 &lt; \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. </p>

CC BY-SA 3.0
2014-03-31T02:43:35.323Z
2014-03-31T14:03:50.067Z
2017-04-13T12:32:28.167Z
Sasho Nikolov
<p>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 &gt; 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.</p>

CC BY-SA 3.0
2014-03-28T18:18:07.577Z
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.
Suresh Venkat
CC BY-SA 3.0
2014-03-28T18:22:27.613Z
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...?
usul
CC BY-SA 3.0
2014-03-28T18:35:17.053Z
The way you defined the guarantees, they would imply NP is in BPP.
Sasho Nikolov
CC BY-SA 3.0
2014-03-29T08:09:53.377Z
@SashoNikolov really ? why so ? The APX-hardness is against PTASs, not necessarily a PRAS, right ?
Suresh Venkat
CC BY-SA 3.0
2014-03-29T15:44:33.447Z
@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.
Sasho Nikolov
CC BY-SA 3.0
2014-03-29T20:35:25.133Z
@SashoNikolov ah I see what you mean. Good point. I think you should convert your comment above (and the explanation above) into an answer.
Suresh Venkat
<cc.complexity-theory><complexity-classes><randomized-algorithms><apx>
PAC algorithms for APX-Hard problems
Daishisan
# PAC algorithms for APX-Hard problems

(Asked by: username_0 on 2014-03-28)

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.

**Tags:** cc.complexity-theory, complexity-classes, randomized-algorithms, apx

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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...?  
> **username_3**: The way you defined the guarantees, they would imply NP is in BPP.  
> **username_1**: @SashoNikolov really ? why so ? The APX-hardness is against PTASs, not necessarily a PRAS, right ?  
> **username_3**: @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.  
> **username_1**: @SashoNikolov ah I see what you mean. Good point. I think you should convert your comment above (and the explanation above) into an answer.  

---

## 1 answers

### Answer by username_3 on 2014-03-31. Score: 4

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](https://cstheory.stackexchange.com/a/21702/4896) to another question. APX-hardness for a problem $P$ implies that there is a [PTAS reduction](http://www.nada.kth.se/~viggo/wwwcompendium/node5.html) 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.


---

