0
$\begingroup$

I know that by definition, all NP problems can be reduced to NP-Complete problems. But does that also applies the other way around?

Can all NP-Complete be reduced to NP problems?

My understanding is that it cannot be done, since that would mean that both are equally complex, therefore NP=NP-Complete.

But the answer to this post seems to point into this direction: Can an NP-Complete problem be reduced to an NP problem?

$\endgroup$
0

2 Answers 2

1
$\begingroup$

Your answer is basically correct. As Arno says, your confusion arises from not being careful with quantifiers. There are two possible versions of the question, and neither you nor the user in the linked thread made it very clear which one is the intended one.

Version 1: "Given an NP-complete problem A, does there exist an NP problem B such that A can be reduced to B?" This is trivially true because you can simply choose B = A.

Version 2: "Given an NP-complete problem A, can A be reduced to every NP problem B? If this were true, it would - as you already noticed - imply that NP = NP-C

$\endgroup$
1
  • $\begingroup$ (There are no threads here, conceptually. Is your intended Your hengxin?) $\endgroup$
    – greybeard
    Commented May 20, 2023 at 16:26
0
$\begingroup$

I know that by definition, all NP problems can be reduced to NP-Complete problems.

This is wrong.

The definition of NP-complete is as follows:

If a problem is NP and all other NP problems are polynomial-time reducible to it, the problem is NP-complete.

By this definition, each NP-complete problem is also an NP problem. But whether NP = NP-complete is unknown. That is, we do not know whether each NP problem is also an NP-complete problem.

$\endgroup$
1
  • $\begingroup$ We know that $\emptyset$ is not NP-complete. $\endgroup$
    – Arno
    Commented May 19, 2023 at 12:54

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.