A language or problem is said to be unapproximable if is not R-approximable for any fixed value . Or otherwise, any poly-time approximation algorithm must give arbitrarily bad solutions for some inputs.
A language or problem is said to be unapproximable if is not R-approximable for any fixed value . Or otherwise, any poly-time approximation algorithm must give arbitrarily bad solutions for some inputs.