Hardness of approximation: what decision problem is hard exactly? 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 &lt; \epsilon &lt; 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.
Most likely what is meant is the following statement:

If $P \ne NP$, then there is no polynomial-time approximation algorithm for Set-Cover that achieves a $(1-\epsilon) \log n$ approximation factor.

Or, equivalently: the existence of a polynomial-time approximation algorithm for Set-Cover that achieves a $(1-\epsilon) \log n$ approximation factor implies that $P=NP$.



Your proposed formulation at the end of your question might look tempting, but if you want to understand how to formalize the claim, I probably wouldn't suggest formalizing it that way -- that formulation introduces unfamiliar technical issues of its own.  The problem you listed is a promise problem (it's not a decision problem).  Promise problems are weird and some of your intuition that you've built up won't work quite right for promise problems.   Promise problems are weird and counter-intuitive; if you want to build your intuition, often it's best to simply avoid them, rather than try to absorb the messy details involved in formalizing them.