0
$\begingroup$

All NP problems can be reduced to NP-Complete problems, can an NP-Complete problem be reduced to a NP problem (non complete)?

$\endgroup$
1
  • $\begingroup$ Are you asking whether, for a given NP-complete problem $NP_C$ there exists any problem $NP_x \in NP, NP_x \ne NP_C$ such that $NP_C$ can be reduced to $NP_x$? That would make $NP_C$ NP-complete, too. And yes, there is more than one NP-complete problem. (Or no, such an $NP_x$ is not non-complete.) $\endgroup$
    – greybeard
    May 20, 2023 at 16:18

1 Answer 1

4
$\begingroup$

An NP-complete problem is in NP, by definition. No reduction needed.

$\endgroup$
2
  • 1
    $\begingroup$ Okay I feel really dumb now! Thanks for making it clear $\endgroup$ Aug 1, 2020 at 3:57
  • 2
    $\begingroup$ @PedroPapel Welcome to Computer Science! please consider accepting this as the answer if it helped you, thank you. $\endgroup$
    – Evil
    Aug 2, 2020 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.