Problem Detail: If an optimization problem is known to be inapproximable up to some precision, does this automatically imply that the problem is apx-hard?
Asked By : mat
Answered By : Yuval Filmus
If P$=$NP then there is a polytime algorithm for any NP optimization problem, and so every problem is APX-hard. So from now on, suppose that P$neq$NP. We can associate with any decision problem $L in NP$ an optimization problem $o_L$ by defining $o_L(x) = 1$ if $x in L$ and $o_L(x) = 2$ otherwise. Suppose $o_L$ reduces to $o_M$ via a PTAS reduction $(f,g,alpha)$ (notation as in the Wikipedia article). Let $C = 1+alpha(1/2)$. Thus if $y$ is a $C$-approximation to $o_M(f(x))$ then $g(x,y,1/2)$ is a $3/2$-approximation to $o_L(x)$, from which we can determine whether $x in L$ or not. Altogether, this gives a polytime reduction from $L$ to $M$. Now take any NP-complete language for $L$ and any NP-intermediate language for $M$ (such a language exists because of Ladner’s theorem). On the one hand, since $M notin P$, you cannot 2-approximate $o_M$. On the other hand, $L$ doesn’t reduce to $M$ (since that would apply that $M$ is NP-complete), and so $o_L$ doesn’t reduce to $o_M$. We conclude that $o_M$ is not APX-hard.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7029 Ask a Question Download Related Notes/Documents