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.

  • $\begingroup$ 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$. $\endgroup$ Mar 23 at 12:41
  • $\begingroup$ Perhaps you need some nontriviality assumption. $\endgroup$ Mar 23 at 12:56
  • $\begingroup$ So what condition is needed to ensure that the polytime reduction exists? $\endgroup$ Mar 23 at 12:59
  • $\begingroup$ Whatever conditions are needed to make this proof go through. $\endgroup$ Mar 23 at 13:00
  • 1
    $\begingroup$ It's the truth value of $f(x) \in M$. $\endgroup$ Mar 23 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.