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.

| cite | improve this question | | | | |
  • $\begingroup$ 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. $\endgroup$ – David Richerby Apr 22 '15 at 11:24
  • $\begingroup$ 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. $\endgroup$ – yuugen Apr 22 '15 at 13:10
  • $\begingroup$ 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. $\endgroup$ – David Richerby Apr 22 '15 at 13:15
  • $\begingroup$ Yes..I can't put my finger on that :(..could you please elaborate $\endgroup$ – yuugen Apr 22 '15 at 13:24
  • 1
    $\begingroup$ Hint: give a counter-example. $\endgroup$ – 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:

Are there problems in NP which are not NP-complete?

Perhaps you can answer this question somehow. Try to think of the simplest possible problems.

| cite | improve this answer | | | | |
  • $\begingroup$ I suggest rephrasing the question as follows: "Are there problems in NP (but not in P) that are not NP-hard?" $\endgroup$ – André Souza Lemos Apr 22 '15 at 21:56
  • $\begingroup$ Well, problems in P can't be NP-hard. Unless P = NP, of course... $\endgroup$ – André Souza Lemos Apr 22 '15 at 21:59
  • $\begingroup$ I am not contesting the exercise, on the contrary. Just suggesting what I think would be a better version of the question, that's all. As it reads now, the answer would be trivially "yes", unless you assume implicitly what I have added. $\endgroup$ – André Souza Lemos Apr 22 '15 at 22:07
  • $\begingroup$ Not to be byzantine, but assuming explicitly that the problem is not in P is, in my opinion, an informative hint that would enhance the educational value of the exercise. $\endgroup$ – André Souza Lemos Apr 22 '15 at 22:24
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – André Souza Lemos Apr 22 '15 at 22:27

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.