Definition
Decision Version of an APX-complete Optimisation Problem
For an APX-complete 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-complete decision problem” is shorthand here, not a standard decision complexity class. APX-completeness concerns approximate optimisation; the threshold question asks for an exact yes/no answer.