APX-complete Decision Problem

Definition

Decision Version of an APX-complete Optimisation Problem

For an APX-complete optimisation problem $\Pi$, its associated decision problem ${\Pi }_{\mathrm{dec}}$ is:

Instance: an instance $I$ of $\Pi$ and a binary-encoded rational threshold $t$.

Question: does a feasible solution meet the threshold?

$$(I,t)\in {\Pi }_{\mathrm{dec}}⟺\exists S\in {\mathcal{S}}_{\Pi }(I):\{\begin{array}{ll}{f}_{\Pi }(I,S)\le t,& \mathrm{goal}=\min ,\\ f_{\Pi }(I,S)\ge t,& \mathrm{goal}=\max .\end{array}$$

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.