Are all NP problems reducible to NPC ?

Question

I am a bit confused in this logic according to me all NPC are NP so that means all NPC are reducible to NP but since NPC are NP-hard as well so I guess that is not possible since if x is reduced to y that means y must be harder than or equal to x that means x cant be NPC since NP-hard is not easier than NP , so is it that all NP are reducible to NPC or all NPC are reducible to NP , I am a bit confused in this , so please help.

Comments

Your question is wrong. The thing is that if you make it correct, you shall get the answer also. 

Are all NP problems reducible to NPC ?

NP Complete is a program class and we cannot reduce a problem to a problem class. 

---

Sir I think you understood where am I going wrong , so please do correct me , I am not getting this , if A is an NP problem and B is NPC so is this stmt wrong

A is reducible to B

Answer 1

Any NP problem is reducible to any NP-Complete problem. Because that is how NP-complete problems are defined.

If a NP-complete problem is reduced to a NP problem, then that NP problem also becomes NP-complete- again, definition of NP-complete problem. 

Comments

Sir just one confusion when we say a given problem is NPC then we first prove it to be NP , so does that mean in proving it to be NP we are reducing it to NP ?

But in the general procedure of proving it to be NP we simply verify the input instance in polynomial time so then is this the same as reducing NPC to NP and if it is than as u said that if NPC is reducible to NP then that problem is also NPC but as such in the proof this doesn't happen .

---

Actually to prove a problem to be in NP-complete we always reduce a NP-complete (which is also NP) to it. If we reduce a NP problem to our problem, our problem becomes NP only. Now, we need to reduce a NP-hard problem to that problem to make it NP-complete as NP-complete is the intersection of NP and NP-hard sets.