Definition
APX-hard Optimisation Problem
Fix PTAS-reductions as the approximation-preserving reduction convention. An optimisation problem
is APX-hard if every problem in APX reduces to it: A PTAS-reduction transforms instances and approximate solutions in polynomial time for each fixed requested accuracy, controlling the error so that a PTAS for
yields one for . Thus a PTAS for
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.