NP-Optimisation Problem

Definition

NP-Optimisation Problem

An NP-optimisation problem is an optimisation problem

$$\Pi =(D_{\Pi },{\mathcal{S}}_{\Pi },f_{\Pi },\mathrm{goal}),\mathrm{goal}\in \{\min ,\max \},$$

where $|I|$ denotes the binary encoding length of $I$:

Component	Meaning	Polynomial-time requirement
$D_{\Pi }$	Valid instances	Decide $I\in D_{\Pi }$
${\mathcal{S}}_{\Pi }(I)$	Feasible solutions of $I$	Decide $S\in {\mathcal{S}}_{\Pi }(I)$
$f_{\Pi }(I,S)\in {\mathbb{Q}}_{\ge 0}$	Objective value of feasible $S$	Compute $f_{\Pi }(I,S)$

Time is measured in the input length: $|I|$ or $|I|+|S|$, respectively. For some fixed polynomial $p$,

$$\forall I\in D_{\Pi }\forall S\in {\mathcal{S}}_{\Pi }(I):|S|\le p(|I|).$$

Task: given $I\in D_{\Pi }$ with ${\mathcal{S}}_{\Pi }(I)\ne \varnothing$, find an optimal solution

$$S^{\ast }\in {\mathcal{S}}_{\Pi }(I),f_{\Pi }(I,S^{\ast })=\underset{S\in {\mathcal{S}}_{\Pi }(I)}{\mathrm{goal}}{f}_{\Pi }(I,S).$$

Intuition

Candidates are short; instance validity, feasibility, and objective value are efficiently checkable. Finding the best candidate need not be efficient. Membership in NP-optimisation alone does not imply NP-hardness.

Decision Version

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}$$

Link to original

Comparison to NP

Both NP and NP-optimisation use polynomially balanced, polynomially decidable instance–candidate relations. NP asks whether an accepting candidate exists; NP-optimisation asks which feasible candidate is best.

	NP	NP-optimisation
Input	Instance $I$	Instance $I$
Output	Yes / no	Optimal solution $S^{\ast }$, or infeasibility
Polynomial-time check	Certificate acceptance	Feasibility and objective value, not optimality
Extra structure	None required	Objective $f_{\Pi }$ and goal $\min$ or $\max$