Do you have to do reduction both ways to prove a problem is NPC?
The answer by Draconis is wrong in &quot;showing that the new problem is NP-hard.&quot; Reducing from something in NP to a new problem does not show NP-hardness. In particular, if a problem A is in P it is also in NP. Suppose there is a reduction from such a polynomial-time solvable A to some new problem B. Then, problem B still can be in P, and in this case B is not NP-hard.
The correct version of this answer says that to show that a new problem is NP-hard one has to reduce from another NP-hard problem A. Then, the new problem cannot be &quot;simpler&quot; than the hardest problem in NP. If it were, then one could solve all NP-hard problems via the new problem, first reducing any problem to A (which is NP-hard by assumption) and then to B.