Content deleted Content added
Rephrased the comments on the use of the term 'optimization problem'. |
Added a separate section for NPO. |
||
Line 13:
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>. For example, if there is a [[Graph (mathematics)|graph]] <math>G</math> which contains vertices <math>u</math> and <math>v</math>, an optimization problem might be "find a path from <math>u</math> to <math>v</math> that uses the fewest edges". This problem might have an answer of, say, 4. A corresponding decision problem would be "is there a path from <math>u</math> to <math>v</math> that uses 10 or fewer edges?" This problem can be answered with a simple 'yes' or 'no'.
=== NP optimization problems ===
An ''NP-optimization problem'' (NPO) is an optimization problem with the following additional conditions.<ref name=Hromkovic>{{citation
| |||