Dark Mode

5,034 views

16 votes

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?

- $Q_1$ is in NP, $Q_2$ is NP hard.
- $Q_2$ is in NP, $Q_1$ is NP hard.
- Both $Q_1$ and $Q_2$ are in NP.
- Both $Q_1$ and $Q_2$ are in NP hard.

0

23 votes

Best answer

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.

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.

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).

1

4 votes

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**