APX-hard Optimisation Problem

Definition

APX-hard Optimisation Problem

Fix PTAS-reductions as the approximation-preserving reduction convention. An optimisation problem $\Pi$ is APX-hard if every problem in APX reduces to it:

$$\forall \Gamma \in \mathrm{APX}:\Gamma {\le }_{\mathrm{PTAS}}\Pi .$$

A PTAS-reduction transforms instances and approximate solutions in polynomial time for each fixed requested accuracy, controlling the error so that a PTAS for $\Pi$ yields one for $\Gamma$.

Thus a PTAS for $\Pi$ would give a PTAS for every APX problem; no APX-hard problem admits a PTAS unless P = NP. APX-hardness does not itself imply membership in APX. Its threshold decision version retains the exact yes/no question, not the approximation guarantee.

An APX-hard problem admits no PTAS unless P = NP.