GATE CS 2003 Q12 — Asymptotic Worst Case Time and Space Complexity

To determine the complexity class of the problem $\Pi$, let us analyze the two polynomial-time reductions provided:

1. Ram's Reduction ($3\text{-SAT} \le_p \Pi$):
   Since $3\text{-SAT}$ is a well-known $\text{NP-complete}$ (and thus $\text{NP-hard}$) problem, reducing $3\text{-SAT}$ to $\Pi$ in polynomial time proves that $\Pi$ is at least as hard as $3\text{-SAT}$. Therefore, $\Pi$ is $\text{NP-hard}$.


2. Shyam's Reduction ($\Pi \le_p 3\text{-SAT}$):
   Since $3\text{-SAT}$ is in $\text{NP}$, and we can reduce $\Pi$ to $3\text{-SAT}$ in polynomial time, it implies that $\Pi$ can be solved by a non-deterministic Turing machine in polynomial time (by first reducing it to $3\text{-SAT}$ and then solving $3\text{-SAT}$). Therefore, $\Pi \in \text{NP}$.

By definition, a decision problem is $\text{NP-complete}$ if and only if it satisfies both conditions:

• It belongs to the class $\text{NP}$ (proven by Shyam).
• It is $\text{NP-hard}$ (proven by Ram).

Thus, we can conclude that $\Pi$ is $\text{NP-complete}$.