# Gap problems clarifation

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$?

-
(i) is definitely false, in fact, if $A$ is in NP then the gap problem is certainly in NP. – 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).
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.)
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. – Jozef Jan 22 '13 at 22:26