# Inapproximability result implies apx-hardness?

If an optimization problem is known to be inapproximable up to some precision, does this automatically imply that the problem is apx-hard?

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.
• I don't see why the existence of a PTAS-reduction from $o_L$ to $o_M$ implies the existence of a polytime reduction from $L$ to $M$. Suppose $L$ is the total set and $M$ is the empty set. Let $q$ be the optimal solution for all instances of $o_L$. If $f$ is the identity function and $g$ fulfills $g(y) = q$ for all $y$, then $f,g$ give a PTAS-reduction from $o_L$ to $o_M$: all solutions are optimal in $o_M$, and these $1$-ratio solutions in $o_M$ are mapped into $1$-ratio solutions in $o_L$. Still, due to the definition of $L$ and $M$, there is no many-one polytime reduction from $L$ to $M$. Mar 23 at 12:41
• It's the truth value of $f(x) \in M$. Mar 23 at 13:26