Content deleted Content added
Adding a link to the first reference of NP-Complete |
|||
Line 59:
* <math>m</math> is [[polynomial time|polynomial-time computable]].
This implies that the corresponding decision problem is in [[NP (complexity)|NP]]. In computer science, interesting optimization problems usually have the above properties and are therefore NPO problems. A problem is additionally called a P-optimization (PO) problem, if there exists an algorithm which finds optimal solutions in polynomial time. Often, when dealing with the class NPO, one is interested in optimization problems for which the decision versions are [[NP-completeness|NP-complete]]. Note that hardness relations are always with respect to some reduction. Due to the connection between approximation algorithms and computational optimization problems, reductions which preserve approximation in some respect are for this subject preferred than the usual [[Turing reduction|Turing]] and [[Karp reduction]]s. An example of such a reduction would be the [[L-reduction]]. For this reason, optimization problems with NP-complete decision versions are not necessarily called NPO-complete.<ref name=Kann92>{{citation
| last1 = Kann | first1 = Viggo
| year = 1992
| |||