Content deleted Content added
mNo edit summary |
Specific notion from complexity theory |
||
Line 1:
In [[computer science]], an '''optimization problem''' is the problem to find among all feasible solutions for some problem the best one. More formally, an optimization problem <math>A</math> is a four-tuple <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;
* given an instance <math>x</math> and a feasible solution <math>y</math> of <math>x</math>, <math>m(x, y)</math> denotes the measure of <math>y</math>, which is usually a positive real.
* <math>g</math> is the goal function, and is either <math>\min</math> or <math>\max</math>.
The goal is then to find for some instance <math>x</math> an ''optimal solution'', that is, a feasible solution <math>y</math> with
<center><math>
m(x, y) = g \{ m(x, y') \mid y' \in f(x) \} .
</math></center>
For each optimization problem, there is a corresponding [[decision problem]] that asks whether there is a feasible solution for some particular measure <math>m_0</math>.
An ''NP optimization problem'' has the following further restrictions:
* <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 synonymous with "NP optimization problem".
[[Category:Computational complexity theory]]
| |||