Definition
Decision Version of an APX-hard Optimisation Problem
For an APX-hard optimisation problem
with a rational-valued objective, its associated decision problem is: Instance: an instance
of and a binary-encoded rational threshold . Question: does a feasible solution meet the threshold?
“APX-hard decision problem” is not a standard classification: APX-hardness belongs to the associated optimisation problem and its approximation-preserving reductions. If
is an NP-optimisation problem, this threshold problem belongs to NP; APX-hardness alone does not supply that membership.