Some Reduction Inferences

 

P, NP, NPC, NPH

• $P$ is a subset of $NP$, but whether $P = NP$ is still not known
• $NPC$ is a subset of $NP$ (only if $P \neq NP$, $NPC$ is a proper subset of $NP$)
• $NPC$ is a proper subset of $NPH$

Reduction

---

Reducing a problem $A$ to problem $B$ means converting an instance of problem $A$ to an instance of problem $B$. Then, if we know the solution of problem $B$, we can solve problem $A$ by using it.

Consider the following example:

---

You want to go from Bangalore to Delhi and you can get a ticket from Mumbai to Delhi. So, you ask your friend for a lift from Bangalore to Mumbai. So, the problem of going from Bangalore to Delhi got reduced to a problem of going from Mumbai to Delhi.

Some Inferences:

---

Consider problems $A$, $B$ and $C$.

Assume all reductions are done in polynomial time.

Two Important Points:

---

1. If $A$ is reduced to $B$ and $B$ $\in$ class $X$, then $A$ cannot be harder than $X$, because we can always do a reduction from $A$ to $B$ and solve $B$ instead of directly solving $A$. This reduction thus gives an upper bound for the complexity of $A$.
2. If $A$ is reduced to $B$ and $A$ $\in$ class $X$, then $B$ cannot be easier than $X$. The argument is exactly same as for the one above. This reduction is used to show if a problem belongs to $NPH$ – just reduce some known $NPH$ problem to the given problem. This reduction thus gives a lower bound for the complexity of $B$.

Somethings to take care of:

---

• If $A$ is reduced to $B$ and $B$ $\in$ $NPC$, then $A$ $\in$ $NP$
  • Here, we cannot say $A$ is $NPC$. All we can say is $A$ cannot be harder than $NPC$ and hence $NP$ (all $NPC$ problems are in $NP$). To belong to $NPC$, all $NP$ problems must be reducible to $A$, which we cannot guarantee from the given statement.
• If $A$ is reduced to $B$, $C$ is reduced to $A$ , $B \in NP $ and $C \in$ $NPC$, then $A$ $\in$ $NPC$
  • Here, the first reduction says that $A$ is in $NP$. The second reduction says that all $NP$ problems can be reduced to $A$ (because $C$ is in $NPC$, by definition of $NPC$, all problems in $NP$ are reducible to $C$ and now $C$ is reduced to $A$). Hence, the two necessary and sufficient conditions for $NPC$ are satisfied and $A$ is in $NPC$
• If $A$ is reduced to $B$ and $B$ $\in$ $NPH$, then $A$ $\in$ $?$
  • Here we can’t say anything about $A$. It can be as hard as $NPH$, or as simple as $P$.