# $L$ APX-hard thus PTAS for $L$ implies $\mathsf{P} = \mathsf{NP}$

If $L$ is an APX-hard language, doesn't the existence of a PTAS for $L$ trivially imply $\mathsf{P} = \mathsf{NP}$?

Since for example metric-TSP is in APX, but it is not approximable within 220/219 of OPT [1] unless $\mathsf{P} = \mathsf{NP}$. Thus if there was a PTAS for $L$ we could reduce metric-TSP using a PTAS reduction to $L$ and thus can approximate OPT within arbitrary precision.

Is my argument correct?

[1] Christos H. Papadimitriou and Santosh Vempala. On the approximability Of the traveling salesman problem. Combinatorica, 26(1):101–120, Feb. 2006.

• Your argument relies on a statement “Metric-TSP is not approximable within a factor of 321/320 unless P=NP,” but this is hardly a trivial statement. (By the way, if you wrote 321/320 because of the paper by Engebretsen and Karpinski, that is for a different problem.) Aug 18 '12 at 3:15
• The point you may be missing is that APX was defined before the PCP theorem was proven. so it makes historical sense to think of the pcp theorem as "a ptas for any apx-hard problem implies p=np" Aug 19 '12 at 18:41