GATE CS 2015 Set 2 Q2 — Regular and Context-free Languages

We are given two polynomial-time reductions:

1. $Q_1 \le_p \text{3-SAT}$: Since $\text{3-SAT}$ is in $\text{NP}$ and the class $\text{NP}$ is closed under polynomial-time reductions, any decision problem that reduces to a problem in $\text{NP}$ must also be in $\text{NP}$. Thus, $Q_1 \in \text{NP}$.
2. $\text{3-SAT} \le_p Q_2$: Since $\text{3-SAT}$ is an $\text{NP}$-complete (and hence $\text{NP}$-hard) problem, reducing it to $Q_2$ in polynomial time establishes that $Q_2$ is at least as hard as $\text{3-SAT}$. Thus, $Q_2$ is $\text{NP}$-hard.

Therefore, $Q_1$ is in $\text{NP}$ and $Q_2$ is $\text{NP}$-hard, which is consistent with Option A.