Optimization problem: Difference between revisions

Revision as of 04:32, 10 December 2006

Revision as of 13:37, 27 September 2007

Line 17:

* 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 synonymously with "NP optimization problem".

==See also==

*[[Mathematical programming]]

[[Category:Computational complexity theory]]