Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
(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).

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.)

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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