Question

A problem P is known to be NP-complete and Q and R are two problems such that Q is polynomial time reducible to P and P is polynomial time reducible to R. Which one of the following is true?

• A. \( Q \) is NP-complete
• B. \( R \) is NP-complete
• C. \( Q \) is NP-hard
• D. \( R \) is NP-hard

Hint:

N/A

Answer 1

The Correct Option is D

Given that \( P \) is NP-complete, we know that every problem in NP is polynomial time reducible to \( P \). Also, since \( P \) is polynomial time reducible to \( R \), it means that \( R \) is at least as hard as NP-complete problems, which makes \( R \) NP-hard. However, we cannot directly conclude that \( R \) is NP-complete unless it is also in NP.
Therefore, the correct answer is 4. \( R \) is NP-hard.