# If an NP problem reduces to an NPC problem, it is NPC?

Is the following statement true?

If a problem P1 is in NP and polynomial time reducible to P2, where P2 is NP-complete, then P1 is also NP-complete.

Intuitively I think the answer is No because I need to prove that it is NP-hard as well for P1 to be NP-complete. But I cannot get the exact proof.

• I'm not sure what you mean by "I need to prove that all NP Hard as well for p1 to be NPC". Informally, saying that a problem is NP-hard is saying "If I could solve this problem, I could solve everything in NP with only a little more work." Does the scenario of this question allow you to do that? Note also that the two possible answers to the question are "Yes, P1 is NP-complete: here's a proof" and "No, his doesn't prove that P1 is NP-complete: here's an explanation of why not." In the negative case, you can't prove that P1 isn't NP-complete because every NPC problem is also reducible to P2. – David Richerby Apr 22 '15 at 11:24
• that was a typo I meant ''it is NP hard as well for p1 to be NPC''(refering to the two properties for a problem to be NPC) @DavidRicherby. – yuugen Apr 22 '15 at 13:10
• OK -- now I understand what you're asking. So, you (correctly) think we're in the "no" case of my comment. You just need to explain why the P1 being polytime reducible to an NP-complete problem isn't a proof that P1 is NP-complete. – David Richerby Apr 22 '15 at 13:15
• Yes..I can't put my finger on that :(..could you please elaborate – yuugen Apr 22 '15 at 13:24
• Hint: give a counter-example. – Raphael Apr 22 '15 at 14:04

Hint: Every problem in NP is reducible to $P_2$. In particular, if $P_1$ is in NP but not NP-complete then it reduces to $P_2$ without being NP-complete. So the question is: