Q. 31 Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to
3-SAT and 3-SAT reduces in polynomial time to Q2. Then which one of following
is consistent with the above statement?
(A) Q1 is in NP, Q2 in NP hard
(B) Q2 is in NP, Q1 is NP hard
(C) Both Q1 and Q2 are in NP
(D) Both Q1 and Q2 are NP hard
Answer: (A)
Explanation:
