[Solved]: $L$ APX-hard thus PTAS for $L$ implies $\mathsf{P} = \mathsf{NP}$

Problem Detail: 

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.

Asked By : jimmy

Answered By : Tsuyoshi Ito

Some people (including more than one moderators) complained to me for posting an answer based on a comment, and I am tired of defending me from them. I asked them to delete this answer.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3245

 Ask a Question

 Download Related Notes/Documents