Let S be an NP-complete problem and Q and R be two other problems not known to…
GATE · 2006 · CS
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?
- A.
R is NP-complete
- B.
R is NP-hard
- C.
Q is NP-complete
- D.
Q is NP-hard
Attempted by 45 students.
Sign up free to check your answer
Sign up freeLoading lesson…