Let S be an NP-complete problem. Q and R are other two problems not known to…
2017
Let S be an NP-complete problem. Q and R are other two problems not known to be NP. Q is polynomial time reducible to S and S is polynomial time reducible to R. Which of the following statements is true?
Answer: B. R is NP-hard — Since S is NP-complete, every problem in the class NP reduces to S by definition. The given reduction S ≤p R implies that every problem in NP also reduces to…
- A.
R is NP-complete
- B.
R is NP-hard
- C.
Q is NP-complete
- D.
Q is NP-hard
Attempted by 6 students.
Show answer & explanation
Correct answer: B
Since S is NP-complete, every problem in the class NP reduces to S by definition. The given reduction S ≤p R implies that every problem in NP also reduces to R, which satisfies the formal definition of an NP-hard problem. Since it is not known if R is in NP, we conclude R is NP-hard.
Explore the full course: Iocl Engineers Officers Grade A Paper 2