Revision as of 20:11, 3 October 2008 edit C. lorenz (talk \| contribs) 353 edits Rephrased and added more precise critera for NPO problems. Reference. ← Previous edit		Revision as of 20:17, 3 October 2008 edit undo C. lorenz (talk \| contribs) 353 edits Rephrased the comments on the use of the term 'optimization problem'. Next edit →
Line 27: * ''m'' is [[polynomial time \| polynomial-time computable]]. This implies that the corresponding decision problem is in [[NP (complexity)\|NP]]. ~~Since~~In computer science, interesting optimization problems usually ~~fulfill~~have ~~these~~the ~~criteria,~~above ~~"optimization~~properties and are therefore NPO problems. A problem" is ~~often~~additionally ~~used~~called ~~synonymously~~a P-optimization (PO) problem if there exists an algorithm which finds optimal solutions in polynomial time. Often, when dealing with ~~"NP~~the class NPO, one is interested in optimization ~~problem"~~problems for which the decision versions are NP-hard. ==See also==

Optimization problem: Difference between revisions