# Why is the language $NP-hard$?

Let's denote $IS(G)$ to be the size of the maximal independent set in $G$. Consider the following language: $$A = \left \{ G\ |\ IS(G)\ge \frac{1}{5}n \right \}$$

I know that $gap-IS [1/8 + \varepsilon , 1/4-\varepsilon]$ is $NP$-hard.

How can I infer that $A$ is $NP$-hard by utilizing the gap problem?

You reduce $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ (for any $\epsilon < 1/20$) to $A$. The reduction is the identity function. Let's see why it works:
• If a graph $G$ is a YES instance of $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ then it has an independent set of size at least $(1/4-\epsilon)n \geq n/5$.
• If a graph $G$ is a NO instance of $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ then it has no independent set of size $(1/8+\epsilon)n < n/5$.
Hence a graph $G$ is a YES instance of $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ if and only if it is a YES instance of $A$.