Consider two decision problems π1,π2 such that π1 reduces in polynomialβ¦
2015
Consider two decision problems π1,π2 such that π1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to π2. Then which one of the following is consistent with the above statement?
- A.
π1 is in NP, π2 is NP hard.
- B.
π2 is in NP, π1 is NP hard.
- C.
Both π1 and π2 are in NP .
- D.
Both π1 and π2 are NP hard.
Attempted by 60 students.
Show answer & explanation
Correct answer: A
Key idea: use the direction of polynomial-time reductions and known facts about 3-SAT.
From Q1 reduces in polynomial time to 3-SAT: If a problem reduces to a problem in NP, then it is also in NP (you can map an instance and run the NP verifier for the target). Since 3-SAT is NP-complete (hence in NP), Q1 is in NP.
From 3-SAT reduces in polynomial time to Q2: Because 3-SAT is NP-hard, any problem that 3-SAT reduces to is also NP-hard. Therefore Q2 is NP-hard.
Conclusion: The statement that Q1 is in NP and Q2 is NP-hard is consistent with the given reductions.
A video solution is available for this question β log in and enroll to watch it.