Optimization problem: Difference between revisions

Revision as of 18:54, 21 March 2006

Revision as of 03:47, 10 December 2006

Line 1:

In [[computer science]], an '''optimization problem''' is the problem toof findfinding amongthe ''best'' solution from all feasible solutions for some problem the best one. More formally, an optimization problem <math>A</math> is a quadruple <math>(I, f, m, g)</math>, where

* <math>I</math> is a set of instances;

* given an instance <math>x \in I</math>, <math>f(x)</math> is the set of feasible solutions;

Line 15:

* <math>I</math> can be recognized in [[polynomial time]], and

* the size of a feasible solution is polynomially bounded by the instance size.

This implies that the corresponding decision problem is in [[NP (complexity)|NP]]. Since interesting optimization problems usually fulfill these criteria, "optimization problem" is often used synonymoussynonymously with "NP optimization problem".

[[Category:Computational complexity theory]]