GATE CS 2006 Q16 — Asymptotic Worst Case Time and Space Complexity

To determine the correct statement, let us analyze the definitions of NP-completeness, NP-hardness, and the properties of polynomial-time reductions ($\le_p$):

1. Analyze problem $S$:

   Since $S$ is NP-complete, it satisfies two conditions:

   • $S \in \text{NP}$
   • $S$ is NP-hard, meaning for every problem $X \in \text{NP}$, $X \le_p S$.
2. Analyze the reduction $S \le_p R$:

   We are given that $S \le_p R$. Since polynomial-time reduction is transitive:

   $$\text{For any } X \in \text{NP}, \quad X \le_p S \quad \text{and} \quad S \le_p R \implies X \le_p R$$

   By definition, any problem to which all problems in NP can be reduced in polynomial time is NP-hard. Therefore, $R$ is NP-hard.

   Since $R$ is not known to be in NP, we cannot conclude that $R$ is NP-complete (which requires being in NP).

3. Analyze the reduction $Q \le_p S$:

   Reducing a problem $Q$ to an NP-complete problem $S$ only tells us that $Q$ is no harder than $S$. It does not show that $Q$ is NP-hard or NP-complete. For example, $Q$ could be a simple problem in $\text{P}$ (since any problem in $\text{P}$ can be reduced to any non-trivial problem in $\text{NP}$).

Thus, the only statement we can definitively assert is that $R$ is NP-hard.