GATE CS 2015 Set 2 Q.12 (CS Q.2): Asymptotic Analysis and Time/Space Complexity

Consider two decision problems $Q_1, Q_2$ such that $Q_1$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_2$ . Then which one of the following is consistent with the above statement?

$Q_1$ is in NP, $Q_2$ is NP hard.

$Q_2$ is in NP, $Q_1$ is NP hard.

Both $Q_1$ and $Q_2$ are in NP.

Both $Q_1$ and $Q_2$ are NP hard.

Official answer and solution

Official answer: A
From: Official GATE 2015 answer key

Solution

Apply the definitions of polynomial-time reductions ( $A \le_p B$ ) and NP-completeness.

We are given:

$Q_1 \le_p \text{3-SAT}$ .
Since 3-SAT is in NP, any problem that polynomial-time reduces to a problem in NP is also in NP. Hence, $Q_1 \in \text{NP}$ .

$\text{3-SAT} \le_p Q_2$ .
Since 3-SAT is an NP-complete problem, any problem to which 3-SAT polynomial-time reduces is at least as hard as 3-SAT. Thus, $Q_2$ is NP-hard.

Combining both conclusions:
' $Q_1$ is in NP, and $Q_2$ is NP-hard.'
This matches option A.

Final answer

Common trap

Reversing the direction of reduction (e.g., claiming $Q_2$ is in NP or $Q_1$ is NP-hard).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 2
Question: 12 of 65, printed as CS Q.2
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source