Abstract: The approximability of NP optimization problems is investigated in this paper. We classify the problems according to their approximability and prove that these classes are different (under the hypothesis P≠NP). In addition, we define a reduction which preserves the approximation ratio among the problems, and find complete problems under this reduction for every class.

Key words: computational complexity, combinatorial optimization, NP completeness

摘要： 研究了NP最优化问题的可近似性。按照不同的可近似性将问题分类，证明了这些类是不同的 （在P≠NP的假设下），并定义了问题之间保持近似比的归约，为每一类找到了在此归约下完 全的问题。

关键词: 计算复杂性, 组合优化, NP完全性