NP-Optimisation Problem

Definition

NP-Optimisation Problem

An NP-optimisation problem is an optimisation problem

where denotes the binary encoding length of :

Component	Meaning	Polynomial-time requirement
	Valid instances	Decide
	Feasible solutions of	Decide
	Objective value of feasible	Compute

Time is measured in the input length: or , respectively. For some fixed polynomial ,

Task: given with , find an optimal solution

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 , the associated decision problem is:

Instance: with and , both binary-encoded.

Question: does a feasible solution meet the threshold?

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	Instance
Output	Yes / no	Optimal solution , or infeasibility
Polynomial-time check	Certificate acceptance	Feasibility and objective value, not optimality
Extra structure	None required	Objective and goal or