Optimization problem: Difference between revisions

Revision as of 16:04, 1 February 2008

Revision as of 20:11, 3 October 2008

Line 14:

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(NPO) is an optimization problem with the following furtheradditional conditions.<ref restrictions:name=Hromkovic>{{citation

| last1 = Hromkovic | first1 = Juraj

* <math>I</math> can be recognized in [[polynomial time]], and

| year = 2002

* the size of a feasible solution is polynomially bounded by the instance size.

| Edition = 2nd

| title = Algorithms for Hard Problems

| series = Texts in Theoretical Computer Science

| publisher = Springer

| isbn = ISBN-13 978-3540441342

}}</ref>

* the size of aevery feasible solution is polynomially bounded by the instance size.,

* the languages <math>I</math> and <math>f(x)</math> can be [[decidable language | recognized]] in [[polynomial time]], and

* ''m'' is [[polynomial time | polynomial-time computable]].

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".