3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If Eq. 34.1 is the same as Lemma 34.1 in the 2nd Ed., this is talking about polynomially related encodings of the same problem - i.e. that we can, within reason, use any encoding and still obtained the same complexity result with respect to polynomial time computability. This is not the same as a reduction between two problems. $\endgroup$ – Luke Mathieson Mar 3 '13 at 4:53
  • $\begingroup$ eq. 34.1 is on pg. 1067, 34.3. I also realized that if we do not also show $L_2 \in $ NP, and if for example, $L_2 \in$ P, then we would have shown a NPC problem reduces to a P problem. $\endgroup$ – T. Webster Mar 6 '13 at 3:04
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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