GATE CSE 2015 | Set 2 | Question: 2

Question

Consider two decision problems $Q_1, Q_2$ such that $Q_1$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_2$. Then which one of the following is consistent with the above statement?

• A. $Q_1$ is in NP, $Q_2$ is NP hard.
• B. $Q_2$ is in NP, $Q_1$ is NP hard.
• C. Both $Q_1$ and $Q_2$ are in NP.
• D. Both $Q_1$ and $Q_2$ are in NP hard.

Comments

why is this question out of syllabus? It comes under undecidability.

---

NP is out of syllabus @Manoja Rajalakshmi A

---

Q1 reduces in polynomial time to 3-SAT 
==> Q1 is in NP

3-SAT reduces in polynomial time to Q2 
==> Q2 is NP Hard.  If Q2 can be solved in P, then 3-SAT
    can be solved in P, but 3-SAT is NP-Complete, that makes 
    Q2 NP Hard

---

is it also out of syllabus ?

Answer 1

3-SAT is NP-Complete and hence in NP as well as NP-hard.

Now, any less or equally hard problem can be reduced (in polynomial time) to 3-SAT. So, Q1 reducing to 3-SAT means Q1 is less harder than 3-SAT- can be P or NP. Since P ⊆ NP. Q1 is in NP, need not be NP-Hard.

3-SAT reducing  (in polynomial time) to Q2 means Q2 is harder or as hard as 3-SAT meaning Q2 is also NP-Hard. Q2, need not be in NP.

So, A option only is always correct.

Comments

@Arjun Sir,  Q2 is NPC which comes in both NP & NP-Hard. But no option is for NPC. So, why not option C?

---

Sir, Q2 is NPC problem(belongs to NP and is NP-hard)?So option C is right??please clear this doubt

How to prove that a given problem is NP complete?

The idea is to take a known NP-Complete problem and reduce it to L.  If polynomial time reduction is possible, we can prove that L is NP-Complete by transitivity of reduction (If a NP-Complete problem is reducible to L in polynomial time, then all problems are reducible to L in polynomial time).

source:https://www.geeksforgeeks.org/np-completeness-set-1/

Answer 2

Golden rule: We only reduce problems to equivalently hard, or harder problems. Reason being that the solution to the problem-in-hand can be used to solve a harder problem.

Let A → B denote A reduces to B. Also, fact: 3-SAT is NPC.

Given that: Q1 → 3-SAT and 3-SAT → Q2.

Clearly, Q2 is at least as hard, or harder than Q1. Option B eliminated

Now, Q1 can't be NPH because Q1 is supposed to be "easier" than NPC. Option D eliminated

Option A and C can both be correct. If we choose C, then it won't be consistent because Q2 is at least as hard, or harder than NPC. Putting Q2 in NP restricts it from being NPH. Hence, A seems more correct.

Option A