I am reading Introduction to Algorithms 3rd for my CS course. Lemma 34.8 says to prove a language $L_2$ NP-complete:
If $L_2$ is a language such that $L_1 \le_P L_2$ for some $L_1 \in$ NPC, then $L_2$ is NP-hard. If, in addition, $L_2 \in $ NP, then $L_2 \in $ NPC.
So by lemma (34.8) we must show:
- Show $L_1 \le_P L_2$. If $L_1 \in$ NPC then $L_2$ is NP-HARD.
- show $L_2 \in$ NP.
I don't see why it necessary to show $L_2 \in$ NP; why isn't it sufficient to just show (1)?
Eq. (34.1) says the reduction function is a bidirectional, one-to-one mapping. So if we can reduce $L_2 \le_P L_1$ (e.g. $f(f(x))^{-1} = x$) in polynomial time and verify $x \in L_1$ in polynomial time (since $L_1 \in$ NPC), why not simply verify $f(x) \in L_2$ in polynomial time as well? Then (2) $L_2 \in$ NP would follow immediately.