摘要
In this paper some undecidable problems on approximability of NP op-timization problems are investigated. In particular, the following problems are all undecidable: (1) Given an NP optimization problem, is it approal-mable in polynomial time? (2) For any polynomialtime computable function r(n), given a polynomial time approkimable NP optimization problem, has it a polynomialtime approximation algorithm with approkimation performance ratio r(n) (r(n)-approkimable)? (3) For any polynomial-time computable func-tions r(n), r'(n), where r'(n) < r(n) a.e., given an r(n)-approkimable NP opti-mization problem, is it r'(n)-approalmable?
In this paper some undecidable problems on approximability of NP op-timization problems are investigated. In particular, the following problems are all undecidable: (1) Given an NP optimization problem, is it approal-mable in polynomial time? (2) For any polynomialtime computable function r(n), given a polynomial time approkimable NP optimization problem, has it a polynomialtime approximation algorithm with approkimation performance ratio r(n) (r(n)-approkimable)? (3) For any polynomial-time computable func-tions r(n), r'(n), where r'(n) < r(n) a.e., given an r(n)-approkimable NP opti-mization problem, is it r'(n)-approalmable?
