NP-Optimisation Problem

computation

Definition

NP-Optimisation Problem

An optimisation problem $\Pi$ is an NP-optimisation problem if:

• $D_{\Pi }$, the set of valid instances, is decidable in polynomial time; $|I|$ is the number of bits needed to write $I$ under binary encoding.
• for each instance $I\in D_{\Pi }$, there is a set ${\mathcal{S}}_{\Pi }(I)$ of feasible solutions;
• every $S\in {\mathcal{S}}_{\Pi }(I)$ has polynomial length, i.e.

$$|S|=|I{|}^{O(1)}$$

• membership $S\in {\mathcal{S}}_{\Pi }(I)$ is decidable in polynomial time;
• the objective function $f_{\Pi }$ is polynomial-time computable and assigns a non-negative rational number to each pair $(I,S)$.

$\Pi$ may be either a minimisation problem or a maximisation problem.

Intuition

An NP-optimisation problem is an optimisation problem whose legal solutions can be checked efficiently.

The definition separates three things:

1. which inputs are valid;
2. which candidate solutions are feasible;
3. how feasible solutions are scored.

The first two parts decide whether a candidate is allowed. The objective function then decides which allowed candidate is better. This is the same pattern as in NP-complete decision problems: a candidate solution should be short enough to write down and easy enough to verify in polynomial time.

So, when one wants to define a new optimisation problem in this class, one usually asks: can an instance be encoded in binary, can a candidate solution be checked quickly, and can its value be computed quickly?

Association with Decision Problem

With every NP-optimisation problem $\Pi$, one can naturally associate a decision problem ${\Pi }_{\text{dec}}$ by giving a bound on the optimal solution:

• The decision version ${\Pi }_{\text{dec}}$ consists of pairs $(I,k)$ with $I$ being an instance of $\Pi$ and $k$ a rational number.
• NP-hardness for ${\Pi }_{\text{dec}}$ implies NP-hardness for $\Pi$.

Comparison to NP

An NP problem is a decision problem.

• input: an instance $I$
• output: yes or no
• witness: a certificate that can be checked in polynomial time

So NP asks whether there exists a certificate proving that the answer is yes.

An NP-optimisation problem is an optimisation problem.

• input: an instance $I$
• output: the best feasible solution
• witness: a feasible solution that can be checked in polynomial time
• extra structure: an objective function that ranks feasible solutions

So NP-optimisation asks which feasible certificate is best.

The associated decision problem asks whether there exists a feasible solution of value at most or at least a bound $k$. That decision version is the part that fits the classical NP framework.

	Classic NP	NP-Optimisation
Input	instance $I$	instance $I$
Output	yes/no	best feasible solution
Witness	a polynomially balanced and polynomially decidable certificate	feasible solution verifiable in polynomial time
Extra	-	objective function ranking feasible solution