Question

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

Hint:

If a known NP-complete problem \( S \) is reducible to another problem \( R \), then \( R \) is at least NP-hard, but it is NP-complete only if it is also in NP.

Answer 1

The Correct Option is B

Step 1: Understanding NP-Completeness and NP-Hardness
- A problem is NP-complete if:
1. It belongs to NP.
2. Every problem in NP is reducible to it in polynomial time.
- A problem is NP-hard if it is at least as hard as any NP problem but may or may not be in NP.

Step 2: Analyzing Given Reductions
- Given that:
1. \( Q \) is polynomial-time reducible to \( S \) (i.e., \( Q \leq_p S \)).
2. \( S \) is polynomial-time reducible to \( R \) (i.e., \( S \leq_p R \)).
- This means that any problem reducible to \( S \) is also reducible to \( R \).
- Since \( S \) is NP-complete, every NP problem is reducible to \( S \), and since \( S \leq_p R \), every NP problem is also reducible to \( R \).
Step 3: Determining the Correct Classification for \( R \)
- Since every NP problem is reducible to \( R \), it means \( R \) is at least NP-hard.
- However, it is not known whether \( R \) is in NP, so it cannot be classified as NP-complete.
Step 4: Evaluating the Options
- (A) Incorrect: \( R \) is NP-hard, but it is not necessarily NP-complete.
- (B) Correct: \( R \) is NP-hard since all NP problems reduce to it.
- (C) Incorrect: \( Q \) is reducible to \( S \), but it does not imply \( Q \) is NP-complete.
- (D) Incorrect: \( Q \) could be in NP, but we do not have sufficient information.