Just a question for personal comprehension.  Consider the following statement:It is NP-hard to approximate Set-Cover within a $(1 - \epsilon) \log n$ factor for any $0 < \epsilon < 1$.Now, NP-hardness refers to decision problems.So what is NP-Hard exactly here ?My guess is that the statement is equivalent to saying that the following problem is NP-hard (but I really ain't sure):Given a set cover instance $S$ and an integer $k$ with the guarantee that either $S$ admits a cover of size at most $k$, or $S$ has a cover of size at least $k \cdot (1 - \epsilon) \log n$, decide if $S$ has a cover of size at most $k$.Note that I took set cover as an example, but my question is on problems that are said 'hard to approximate' in general.
Hardness of approximation: what decision problem is hard exactly?
complexity theory;np hard;approximation
Your guess is correct. The formal statement corresponding to the informal one goes like this:For every $\epsilon > 0$ and every language $L$ in NP there exists a polytime reduction $f$ mapping instances of $L$ to instances of set cover $(F,m)$ (where $F$ is a set system and $m$ is the target number of sets) such that:If $x \in L$ then $f(x)$ has a cover with $m$ sets, andIf $x \notin L$ then every cover of $f(x)$ requires at least $(1-\epsilon)\ln n \cdot m$ sets, where $n$ is the size of the universe.For this more accurate version, see Claim 4.2 in Dana Moshkovitz, The projection games conjecture and the NP-hardness of $\ln n$-approximating set cover.A statement claiming that a certain approximation problem is NP-hard to approximate better than some factor should always be interpreted in this way.