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.8k 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.7k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories