Some Undecidable Problems on Approximability of NP Optimization Problems

Abstract
In this paper some undecidable problems on approximability of NP optimization problems are investigated. In particular, the following problems are all undecidable: (1) Given an NP optimization problem, is it approalmable 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 polynomialtime computable func…

