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.
6
-
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$– Suresh VenkatMar 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$– usulMar 28, 2014 at 18:22
-
2$\begingroup$ The way you defined the guarantees, they would imply NP is in BPP. $\endgroup$– Sasho NikolovMar 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$– Sasho NikolovMar 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$– Suresh VenkatMar 29, 2014 at 20:35
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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.
answered Mar 31, 2014 at 2:43