-
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?
-
- R is NP-complete
- R is NP-hard
- Q is NP-complete
- Q is NP-hard
- R is NP-complete
Correct Option: B
(A) Incorrect because R is not in NP. A NP Complete problem has to be in both NP and NP-hard.
(B) Correct because a NP Complete problem S is polynomial time educable to R.
(C) Incorrect because Q is not in NP.
(D) Incorrect because there is no NP-complete problem that is polynomial time Turing-reducible to Q.
