Q2

MCQ1 mark, −0.33

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?

(A)

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

(B)

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

(C)

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

(D)

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

Loading…