APX Decision Problem

Definition

Decision Version of an APX Optimisation Problem

For an APX 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 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.