Definition
Decision Version of an APX Optimisation Problem
For an APX optimisation problem
, its associated decision problem is: Instance: an instance
of and a binary-encoded rational threshold . Question: does a feasible solution meet the threshold?
This is an NP-optimisation decision problem, hence belongs to NP. “APX decision problem” is shorthand here for this association, not a standard decision complexity class: APX describes approximation of the optimisation problem, not exact threshold decisions.