Some Undecidable Problems on Approximability of NP Optimization Problems

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…