Final answer:
The correct answer is (B) Q2 is in NP, Q1 is NP hard.Based on the reductions given between Q1, 3-SAT, and Q2, Q1 is in NP, and Q2 is NP-hard, which aligns with option (A).
Step-by-step explanation:
If decision problem Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2, then it is possible to infer certain things about the complexity classes of Q1 and Q2. Since 3-SAT is a well-known NP-complete problem, any problem to which 3-SAT can be reduced in polynomial time is at least as hard as 3-SAT, meaning that Q2 is NP-hard. Conversely, if Q1 can be reduced to 3-SAT, this implies that Q1 is at most as hard as 3-SAT, and since 3-SAT is in NP, Q1 is also in NP. Therefore, Q1 is in NP, Q2 is NP-hard, which is consistent with option (A).
This is consistent with the statement that Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. If Q1 is in NP, then it means that there exists a non-deterministic polynomial time Turing machine that can decide the language of Q1. On the other hand, if 3-SAT reduces in polynomial time to Q2, it means that Q2 is at least as hard as 3-SAT. Therefore, Q1 is NP hard.
Hence, Q2 is in NP and Q1 is NP hard.