- $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:
- 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$.
- 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$.
