Content deleted Content added
m Date the maintenance tags or general fixes, Replaced: date={{subst:CURRENTMONTHNAME}} {{subst:CURRENTYEAR}} → date=January 2008 |
wlnk |
||
Line 12:
</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>. 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'.
An ''NP optimization problem'' has the following further restrictions:
| |||