5

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?

Mostafa
  • 2,104
  • 10
  • 28

1 Answers1

3

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).
Mostafa
  • 2,104
  • 10
  • 28
user3680510
  • 3,655
  • 6
  • 26