Let S be an NP-complete problem and Q and R be two other problems not known to…

Answer: R is NP-hard.

• Key facts: S is NP-complete, so S is in NP and every problem in NP reduces to S.

• Transitivity of reductions: because S polynomial-time reduces to R, any NP problem reduces to S and then to R; therefore every NP problem reduces to R, which means R is NP-hard.

• Why not NP-complete: NP-complete also requires the problem to be in NP. The statement does not tell us whether R is in NP, so we cannot conclude R is NP-complete.

• About Q: Q reduces to S (Q ≤p S). This only shows Q is at most as hard as S; it does not show Q is NP-hard or NP-complete. To prove Q is NP-hard one would need reductions from every NP problem to Q (for example S ≤p Q), and to prove NP-complete Q would also need to be shown to be in NP.