5
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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).
| improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mostafa May 6 at 6:50
  • $\begingroup$ yes that is correct $\endgroup$ – user3680510 May 6 at 6:54
  • $\begingroup$ So, I edit your answer based on that. $\endgroup$ – Mostafa May 6 at 7:29

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.