NP-Optimisation Decision Problem

Definition

NP-Optimisation Decision Problem

For an NP-optimisation problem , the associated decision problem is:

Instance: with and , both binary-encoded.

Question: does a feasible solution meet the threshold?

Membership in NP

The solution is a polynomial-length certificate; feasibility and the threshold comparison are polynomial-time checkable. Hence , the class of NP decision problems.

Hardness Transfer

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