World's most popular travel blog for travel bloggers.

[Solved]: If an NP problem reduces to an NPC problem, it is NPC?

, , No Comments
Problem Detail: 

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.

Asked By : madcracker

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback