I read in many places that some problems are difficult to approximate (it is NP-
ID: 648012 • Letter: I
Question
I read in many places that some problems are difficult to approximate (it is NP-hard to approximate them). But approximation is not a decision problem: the answer is a real number and not Yes or No. Also for each desired approximation factor, there are many answers that are correct and many that are wrong, and this changes with the desired approximation factor!
So how can one say that this problem is NP-hard?
(inspired by the second bullet in How hard is counting the number of simple paths between two nodes in a directed graph?)
Explanation / Answer
Usually what's shown is the NP-hardness of a "Gap" version of the problem. For example, suppose that you want to show that it's hard to approximate SET COVER to within a factor of 2.
You define the following "promise" instance of SET COVER that we'll call 2-GAP-SET-COVER:
Fix some number ?. 2-GAP-SET-COVER consists of all instances of set cover where the size of the optimal set cover is either:
at most ?
at least 2?
Suppose we show that the problem of deciding which of the two cases a problem falls into is NP-complete. Then we've shown that approximating SET COVER to within a factor of 2 is NP-hard, because we could use such an algorithm to distinguish these two cases.