Skip to main content
Tweeted twitter.com/#!/StackCompSci/status/237836236159594496
deleted 28 characters in body
Source Link
Juho
  • 22.8k
  • 7
  • 62
  • 117

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] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario SzegedyChristos H. Proof verificationPapadimitriou and the hardness of approximation problemsSantosh Vempala. JOn the approximability Of the traveling salesman problem. ACM 45Combinatorica, 3 26(May 19981):101–120, 501-555Feb. 2006.

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] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM 45, 3 (May 1998), 501-555.

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.

edited title
Link
Juho
  • 22.8k
  • 7
  • 62
  • 117

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

added ref, unified formatting
Source Link
Juho
  • 22.8k
  • 7
  • 62
  • 117

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

Since for example metric-TSP is in APX, but it is not approximable within 220/219 ofof OPT [1] unless P = NP, thus a$\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] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM 45, 3 (May 1998), 501-555.

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

Since for example metric-TSP is in APX, but it is not approximable within 220/219 of OPT unless P = NP, thus a 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?

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] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM 45, 3 (May 1998), 501-555.

deleted 3 characters in body
Source Link
jimmy
  • 23
  • 3
Loading
Source Link
jimmy
  • 23
  • 3
Loading