# If a problem is inapproximable for $(2-\epsilon)$, can we conclude there exists no PTAS for it?

If we prove that:

The existance of a $$(2-\epsilon)$$-approximation algorithm for Problem P1 implies $$P = NP$$,

can we conclude:

There exists no PTAS for Problem P1, and so P1 is APX-hard?

You can conclude There exists no PTAS for Problem P1 if $$P \neq NP$$, but you can NOT conclude P1 is APX-hard. Precisely:

1. If someone proofs $$P = NP$$ you get a trivial PTAS;
2. Assumung $$P \neq NP$$, it still could be APX-intermediate (see https://en.wikipedia.org/wiki/APX#APX-intermediate).
• Thanks. So, based on the Wiki page, we cannot expect to find a PTAS for Problem P1, but it doesn't mean it is APS-hard. Am I right? – Mostafa May 6 at 6:50
• yes that is correct – user3680510 May 6 at 6:54
• So, I edit your answer based on that. – Mostafa May 6 at 7:29