更改

给定<math>I</math>中的一个实例，<math>f(x)</math>是可行解的有限集合；

给定<math>I</math>中的一个实例，<math>f(x)</math>是可行解的有限集合；

* given an instance <math>x</math> and a feasible solution <math>y</math> of <math>x</math>, <math>m(x, y)</math> denotes the [[Measure (mathematics)|measure]] of <math>y</math>, which is usually a [[Positive (mathematics)|positive]] [[Real number|real]].

* given an instance <math>x</math> and a feasible solution <math>y</math> of <math>x</math>, <math>m(x, y)</math> denotes the [[Measure (mathematics)|measure]] of <math>y</math>, which is usually a [[Positive (mathematics)|positive]] [[Real number|real]].

给定一个实例<math>x</math>和一个可行解<math>y</math>，<math>m(x,y)</math>表示<math>y</math>的度量，其通常是一个正实数。

给定一个实例<math>x</math>和一个可行解<math>y</math>，<math>m(x,y)</math>表示<math>y</math>的<font color="#32cd32"> 度量，其通常是一个正实数。</font>

 

* <math>g</math> is the goal function, and is either <math>\min</math> or <math>\max</math>.

* <math>g</math> is the goal function, and is either <math>\min</math> or <math>\max</math>.

<math>g</math>是目标函数，可以是求最小值也可以是最大值。

<math>g</math>是目标函数，可以是求最小值也可以是最大值。

然后，我们的目标是找到一个最优解<math>x</math>，也就是一个可行的解<math>y</math>。

然后，我们的目标是找到一个最优解<math>x</math>，也就是一个可行的解<math>y</math>。

 

An NP-optimization problem (NPO) is a combinatorial optimization problem with the following additional conditions. Note that the below referred polynomials are functions of the size of the respective functions' inputs, not the size of some implicit set of input instances.

An NP-optimization problem (NPO) is a combinatorial optimization problem with the following additional conditions. Note that the below referred polynomials are functions of the size of the respective functions' inputs, not the size of some implicit set of input instances.

NP优化问题（NPO）是一个具有以下附加条件的组合优化问题。<ref name="Hromkovic02">{{citation|last1=Hromkovic|first1=Juraj|title=Algorithmics for Hard Problems|year=2002|series=Texts in Theoretical Computer Science|edition=2nd|publisher=Springer|isbn=978-3-540-44134-2}}</ref>注意，下面提到的多项式是相应函数输入大小的函数，而不是某些隐式输入实例集大小的函数。

<font color="#32cd32"> NP优化问题（NPO）是一个具有以下附加条件的组合优化问题。<ref name="Hromkovic02">{{citation|last1=Hromkovic|first1=Juraj|title=Algorithmics for Hard Problems|year=2002|series=Texts in Theoretical Computer Science|edition=2nd|publisher=Springer|isbn=978-3-540-44134-2}}</ref>注意，下面提到的多项式是相应函数输入大小的函数，而不是某些隐式输入实例集大小的函数。

在<math>f(x)</math>中，对给定实例的大小<math>x</math>中，每个可行解的大小都是多项式有界的，

在<math>f(x)</math>中，对给定实例的大小<math>x</math>中，每个可行解的大小都是多项式有界的，

* the languages <math>\{\,x\,\mid\, x \in I \,\}</math> and <math>\{\,(x,y)\, \mid\, y \in f(x) \,\}</math> can be [[Decidable language|recognized]] in [[polynomial time]], and

* the languages <math>\{\,x\,\mid\, x \in I \,\}</math> and <math>\{\,(x,y)\, \mid\, y \in f(x) \,\}</math> can be [[Decidable language|recognized]] in [[polynomial time]], and

语言<math>\{\,x\,\mid\,x\ in I\,\}</math>和<math>f(x)\,\}</math>中的<math>\{\,(x,y)\,\mid\,y\</math>在[[多项式时间]]内可以[[可判定语言|识别]]，并且，

语言<math>\{\,x\,\mid\,x\ in I\,\}</math>和<math>f(x)\,\}</math>中的<math>\{\,(x,y)\,\mid\,y\</math>在多项式时间内可以可判定语言/识别，并且，</font>

* <math>m</math> is [[Polynomial time|polynomial-time computable]].

* <math>m</math> is [[Polynomial time|polynomial-time computable]].

<math>m</math>是可计算的多项式时间。

<math>m</math>是可计算的多项式时间。

 

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|Karp reductions]]. 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|title=On the Approximability of NP-complete Optimization Problems|year=1992|publisher=Royal Institute of Technology, Sweden|isbn=91-7170-082-X}}</ref>

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|Karp reductions]]. 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|title=On the Approximability of NP-complete Optimization Problems|year=1992|publisher=Royal Institute of Technology, Sweden|isbn=91-7170-082-X}}</ref>

这意味着相应的决策问题在NP中。在计算机科学中，有趣的优化问题通常具有上述性质，因此是NPO问题。如果存在一种在多项式时间内找到最优解的算法，则该问题又称为'''<font color="#FF8000">P-优化（PO）问题 P-optimization problem </font>'''。通常，在处理NPO类问题时，人们对决策版本为NP完全的优化问题感兴趣。请注意，硬度关系总是与某些降低有关。由于近似算法和计算优化问题之间的联系，在某些方面保持近似性的缩减比通常的'''<font color="#FF8000">图灵和卡普约化 Turing and Karp Reductions </font>'''更为可取。这种减少的一个例子就是'''<font color="#FF8000">L-约化  L-reduction </font>'''。因此，具有NP完全决策版本的优化问题不一定称为NPO完全问题。<ref name="Kann92">{{citation|last1=Kann|first1=Viggo|title=On the Approximability of NP-complete Optimization Problems|year=1992|publisher=Royal Institute of Technology, Sweden|isbn=91-7170-082-X}}</ref>

这意味着相应的决策问题在NP中。在计算机科学中，有趣的优化问题通常具有上述性质，因此是NPO问题。如果存在一种在多项式时间内找到最优解的算法，则该问题又称为'''<font color="#FF8000">P-优化（PO）问题 P-optimization problem </font>'''。通常，在处理NPO类问题时，人们对决策版本为NP完全的优化问题感兴趣。请注意，硬度关系总是与某些降低有关。由于近似算法和计算优化问题之间的联系，在某些方面保持近似性的缩减比通常的'''<font color="#FF8000">图灵和卡普约化 Turing and Karp Reductions </font>'''更为可取。这种减少的一个例子就是'''<font color="#FF8000">L-约化  L-reduction </font>'''。因此，具有NP完全决策版本的优化问题不一定称为NPO完全问题。<ref name="Kann92">{{citation|last1=Kann|first1=Viggo|title=On the Approximability of NP-complete Optimization Problems|year=1992|publisher=Royal Institute of Technology, Sweden|isbn=91-7170-082-X}}</ref>

 

* ''NPO(V)'': :The class of NPO problems with polynomial-time algorithms approximating the optimal solution by a ratio bounded by some function on n. In Hromkovic's book, all NPO(IV)-problems  are excluded from this class unless P=NP. Contains the [[Travelling salesman problem|TSP]] and [[Clique problem|Max Clique problems]].

* ''NPO(V)'': :The class of NPO problems with polynomial-time algorithms approximating the optimal solution by a ratio bounded by some function on n. In Hromkovic's book, all NPO(IV)-problems  are excluded from this class unless P=NP. Contains the [[Travelling salesman problem|TSP]] and [[Clique problem|Max Clique problems]].

''NPO(V)''：多项式时间算法的一类NPO问题，以某个函数限定的比率来逼近最优解。在Hromkovic的书中，除非P=NP，否则所有NPO(IV)-问题都不属于这类问题。包含旅行商问题| TSP和集团问题|最大集团问题。

''NPO(V)''：多项式时间算法的一类NPO问题，以某个函数限定的比率来逼近最优解。在Hromkovic的书中，除非P=NP，否则所有NPO(IV)-问题都不属于这类问题。包含旅行商问题| TSP和集团问题|最大集团问题。

如果对于每个实例<math>x</math>和<math>f(x)</math>中的每个解<math>y\in f(x)<math>，<math>m(x,y) , M(x,y)</math>被一个大小为<math>x</math>的多项式函数所限制，则NPO问题称为多项式有界（PB）。NPOPB 类是一类多项式有界的 NPO 问题。

如果对于每个实例<math>x</math>和<math>f(x)</math>中的每个解<math>y\in f(x)<math>，<math>m(x,y) , M(x,y)</math>被一个大小为<math>x</math>的多项式函数所限制，则NPO问题称为多项式有界（PB）。NPOPB 类是一类多项式有界的 NPO 问题。