[Solved]: Inapproximability result implies apx-hardness?

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