patternMinor
Hardness of approximation: what decision problem is hard exactly?
Viewed 0 times
problemwhatapproximationhardnessharddecisionexactly
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#50195, answer score: 3
Revisions (0)
No revisions yet.