why is it necessary to show NP in order to show NPC?

Question

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:

1. Show $L_1 \le_P L_2$. If $L_1 \in$ NPC then $L_2$ is NP-HARD.
2. 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.

Answer 1

In general, the mapping is not one-to-one (Eq. 34.1, whatever that is (can you add it?) cannot be the general case), it's many-to-one, i.e. several instances of $L_{1}$ can map to a single instance of $L_{2}$, in which case you don't get the inverse mapping (at least not immediately from $f$). Furthermore, $f$, even if one-to-one, may not be onto, in which case you cannot map all instances of $L_{2}$ to something in $L_{1}$ (via $f^{-1}$).

If you do happen to have that $f$ is a bijection, then you can do what you propose and you effectively show conditions (1) and (2) in one step - of course you have to prove that your $f$ is a bijection.

Answer 2

Even if $f$ is a bijection, the argument won't work unless the inverse bijection $f^{-1}$ is computable in polynomial time. That is not known (and not likely) to follow from polynomial-time computability of $f$ (though it would be true if $P=NP$, but then you wouldn't be interested in NP completeness, would you?).