$ L $ APX-hard così PTAS a $ L $ implica $ \ mathsf {P} = \ mathsf {} $ NP

Question

Se $ L $ è un linguaggio APX-hard, non si l'esistenza di un PTAS a $ L $ banalmente implicare $ \ mathsf {P} = \ {mathsf NP} $?

Dato che ad esempio metrico-TSP è in APX, ma non è approssimabili entro 220/219 di OPT [1] a meno che $ \ mathsf {P} = \ {mathsf NP} $. Così se ci fosse un PTAS a $ L $ potremmo ridurre metrico-TSP con una riduzione PTAS a $ L $ e quindi in grado di approssimare OPT all'interno di precisione arbitraria.

La mia tesi è corretta?

---

[1] Christos H. Papadimitriou e Santosh Vempala. Sulla approssimabilità Del problema del commesso viaggiatore. Combinatorica, 26 (1): 101-120, febbraio 2006.

Answer 1

Alcune persone (tra cui più di un moderatori) si lamentava con me per la pubblicazione di una risposta basata su un commento, e sono stanco di me difendere da loro. Ho chiesto loro di eliminare questa risposta.