159k views
4 votes
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? (GATE CS 2006)

(A) R is NP-complete

(B) R is NP-hard

(C) Q is NP-complete

(D) Q is NP-hard

User Conetfun
by
7.4k points

1 Answer

3 votes

Final answer:

Given the polynomial-time reductions between Q, S, and R, and the fact that S is NP-complete, it can be concluded that R is NP-hard because it can solve S, and therefore any problem in NP. However, we cannot conclude that R is NP-complete or Q is NP-complete or NP-hard with the information provided.

Step-by-step explanation:

The question concerns the theory of computational complexity, specifically related to NP-completeness and NP-hardness. The given information is that S is an NP-complete problem, Q is polynomial-time reducible to S, and S is polynomial-time reducible to R. Given these reductions, we can determine certain properties about these problems.

Since S is NP-complete, any problem in NP can be reduced to it in polynomial time. Now, since Q can be reduced to S in polynomial time, it suggests that Q may be no harder than S, in terms of computational complexity. However, we do not know if Q is in NP, therefore, we cannot conclude that Q is NP-complete. Hence, option (C) is likely incorrect, and we do not have enough information to say Q is even in NP or not, making option (D) also uncertain.

On the other hand, since S can be reduced to R in polynomial time, and S is an NP-complete problem (hence very hard), R can solve not just S but any problem in NP if it can solve S in polynomial time.

This implies that R is at least as hard as the hardest problems in NP, which is the definition of NP-hardness. Consequently, option (B) R is NP-hard is the correct statement. Although R is NP-hard, we cannot say it is NP-complete as we do not know whether R is in NP; hence, option (A) is incorrect as well.

User PhilHibbs
by
7.4k points