Re: Reductions in P

ahuznot@xxxxxxxxx writes:

We know that if one wants to prove a problem X to be NP-complete,
suffices to take a known NP-complete problem and reduce it to X, by
means of a polynomial-time reduction.


This only shows NP-hardness of X. For NP-completeness, you also have
to show X\in NP.
.