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?
Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.Sign up to join this community
You can conclude There exists no PTAS for Problem P1 if $P \neq NP$, but you can NOT conclude P1 is APX-hard. Precisely: