Here's a simple question which made me confused.

Please tell me if my analysis of the problem and my conclusions are correct.

For an optimization problem $\sf Gap-A[a,b] \in L$ for $b>a$. I want to discuss what I can know about $\sf Gap-A[a/2,b/2]$.

$\sf(i)$ Is it correct to say that $\sf Gap-A[a/2,b/2]$ is not in $\sf NP-Hard$ and it is easy only because the realtion $\frac{a/2}{b/2}=\frac{a}{b}$ and we already know that it is easy to approximate $A$ with factor of $a/b$?

$\sf (ii)$ Is it true that I can't say though that $\sf Gap-A[a/2,b/2]$ is in $\sf L$ since there is no intersection between the gaps? In order that gap $B$ would be in the exact class that gap $A$ is in, we have to have $A \subseteq B$?

  • 1
    $\begingroup$ (i) is definitely false, in fact, if $A$ is in NP then the gap problem is certainly in NP. $\endgroup$ – Yuval Filmus Jan 22 '13 at 18:11

You are confusing NP and NP-hard. The fact that a problem is (say) in L doesn't preclude it being in NP, in fact, quite the contrary: any problem which is in L is a fortiori in NP, i.e. L$\subseteq$NP. On the other hand, it is not likely to be NP-hard (and assuming that P$\neq$NP, if it is in L then it cannot be NP-hard).

Another mistake you're making is that a problem which is approximable can't be NP-hard (or rather, its decision version can't be NP-hard). Considering MAX-3SAT, there is a trivial 7/8-approximation algorithm (pick a random assignment; this can be derandomized), yet the decision version 3SAT is NP-complete.

You're right that GAP-A$(a,b)$ being easy doesn't imply that GAP-A$(a/2,b/2)$ is easy. One example (replacing $1/2$ with an arbitrary $c$) is MAX-2SAT. GAP-2SAT$(a,1)$ is easy for any $a<1$, yet there exist some $b,c$ for which GAP-2SAT$(b,c)$ is NP-hard. (Unfortunately, $c=1/2$ doesn't work, since every 2SAT instance can be $1/2$-satisfied.)

  • $\begingroup$ I am sorry, I indeed meant $NP-hard$, can you please edit your answer after the correction? I don't want to get confused more that I am not. Thank you. $\endgroup$ – Jozef Jan 22 '13 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.