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?

Answer: A. ๐‘„1 is in NP, ๐‘„2 is NP hard. โ€” 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โ€ฆ

  1. A.

    ๐‘„1 is in NP, ๐‘„2 is NP hard.

  2. B.

    ๐‘„2 is in NP, ๐‘„1 is NP hard.

  3. C.

    Both ๐‘„1 and ๐‘„2 are in NP .

  4. D.

    Both ๐‘„1 and ๐‘„2 are NP hard.

Attempted by 70 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.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lessonโ€ฆ