2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 18, 2012 at 3:15
  • $\begingroup$ 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" $\endgroup$
    – Sasho Nikolov
    Commented Aug 19, 2012 at 18:41

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ In case anyone is wondering what I am referring to in the paragraph “However, according to your comment…,” that part became incomprehensible because someone (presumably some moderator) deleted comments by jimmy and me on the question after I posted this answer. $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 21, 2012 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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