# Reduction of np to npc

Given that $$A$$ is $$NPC$$ problem. And I need to check "if $$D$$ belongs to $$NP$$ and $$D\leq_p^\mathsf{}A$$ then $$D$$ is $$NPC$$" is true or not?

My approach: Since $$D\leq_p^\mathsf{}A$$, therefore $$A$$ is at least as hard as $$D$$, and given $$A$$ is $$NPC$$, consequently $$D$$ could be like easy problem $$P, NP.$$ And to prove $$D$$ is $$NPC$$ we need to proof $$D$$ is $$NPH$$ but I am unable to proven. Therefore $$D$$ can't be $$NPC.$$

Don't know my approach and result is right or not. If I did anything wrong please correct me.

Saying that $$D$$ could be in $$P$$ does not disprove "$$D$$ is $$\mathsf{NP}$$-complete" since it could be the case that $$\mathsf{P}=\mathsf{NP}$$.
However the claim is false regardless of the $$\mathsf{P}$$ vs $$\mathsf{NP}$$ matter. Simply pick $$D=\emptyset$$ and $$A$$ as any $$\mathsf{NP}$$-complete problem. Clearly $$D$$ cannot be $$\mathsf{NP}$$-complete since it is not $$\mathsf{NP}$$-hard. To see that $$D$$ is not $$\mathsf{NP}$$-hard notice that, given any language $$B \in\mathsf{NP} \setminus \{\emptyset\}$$, it is false that $$B \le_p D$$.
• I'm not sure what you're asking. It is false that, given any two problems $A,B \in \mathsf{NP}$, you have $A \le_p B$. I don't know if this answers your question or how this relates to my answer. Oct 17 '21 at 22:09