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.

$\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$ Aug 18 '12 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$ Aug 19 '12 at 18:41
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.

$\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$ Aug 21 '12 at 0:06

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.