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$.

  • $\begingroup$ you mean if any two problem exists in NP, the reduction between them isn't not possible ? $\endgroup$
    – Punia
    Oct 17 '21 at 22:05
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Oct 17 '21 at 22:09
  • $\begingroup$ my approach is right? $\endgroup$
    – Punia
    Oct 17 '21 at 22:12

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.