Consider two decision problems 𝑄1,𝑄2 such that 𝑄1 reduces in polynomial…

PYQ GATE 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?

  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 117 students.

Sign up free to check your answer

Sign up free

Explore the full course: Theory Of Computation

Loading lesson…