recategorized by
6,413 views
16 votes
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?

  1. $Q_1$ is in NP, $Q_2$ is NP hard.
  2. $Q_2$ is in NP, $Q_1$ is NP hard.
  3. Both $Q_1$ and $Q_2$ are in NP.
  4. Both $Q_1$ and $Q_2$ are in NP hard.
recategorized by

2 Answers

Best answer
23 votes
23 votes
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.
selected by
4 votes
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

 

Answer:

Related questions

6 votes
6 votes
1 answer
2
28 votes
28 votes
6 answers
3
go_editor asked Feb 12, 2015
12,756 views
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $n$ vertices, $n$ isA multiple of 4EvenOddCongruent to 0 $mod$ 4...
13 votes
13 votes
5 answers
4