0
$\begingroup$

If $R$ is an arbitrary decision problem that is reducible to $S$, which is an NP-complete problem, what can be said about $R$?

I think we should be able to say that $R$ is in NP since an instance of $S$ can have a certificate verified in polynomial time and from the reduction $R \le S$, we could say the same about $R$. Is this reasoning valid? Would it also work if $S$ was only supposed to be in NP rather than NP-complete?

Thanks in advance.

$\endgroup$

1 Answer 1

2
$\begingroup$

Yep - your reasoning regarding your NP is correct. But not regarding NP-complete. The crux of the matter is that NP is inclusive, P is in NP and your problem R could be in P (and thus in NP).

NP-complete is not inclusive. It refers to the hardest problems in NP and a problem is in NP is there is no "simpler solution" (assuming P!=NP). In your case since R < S it may be (temporarily) true that R is in NP-complete, but then you will have to show that there is no simpler solution to R. What you have shown is that there is a solution to R going through S - this is a solution, but for NP-complete, you must show also there there is no simpler solution. (Caveat - all this language of simpler solution, hardest problem, and so on assumes that P!=NP.

$\endgroup$

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.