NP-Optimisation Decision Problem

Definition

NP-Optimisation Decision Problem

For an NP-optimisation problem $\Pi =(D_{\Pi },{\mathcal{S}}_{\Pi },f_{\Pi },\mathrm{goal})$, the associated decision problem ${\Pi }_{\mathrm{dec}}$ is:

Instance: $(I,k)$ with $I\in D_{\Pi }$ and $k\in \mathbb{Q}$, both binary-encoded.

Question: does a feasible solution meet the threshold?

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

Membership in NP

The solution $S$ is a polynomial-length certificate; feasibility and the threshold comparison are polynomial-time checkable. Hence ${\Pi }_{\mathrm{dec}}\in \mathrm{NP}$, the class of NP decision problems.

Hardness Transfer

An exact optimiser answers the threshold question by comparing the optimum with $k$ (or reporting infeasibility). Thus NP-hardness transfers from decision to optimisation:

$${\Pi }_{\mathrm{dec}}\text{ is NP-hard}⟹\Pi \text{ is NP-hard}.$$