|
|
| Line 1: |
Line 1: |
| | $P \subseteq NP \subseteq NPC \subseteq NPH$ | | $P \subseteq NP \subseteq NPC \subseteq NPH$ |
| | + | |
| | + | ==Reduction== |
| | + | Reducing a problem A to problem B means converting an instance of problem A to problem B. Then, if we know the solution of problem B, we can solve problem A. |
| | + | Consider the following example: |
| | + | You want to go from Bangalore to Delhi and you have a ticket from Mumbai to Delhi. So, you get a ticket from Bangalore to Mumbai. So, the problem of going from Bangalore to Delhi got reduced to a problem of going from Mumbai to Delhi. |
| | + | |
| | + | ===2 Important Points=== |
| | + | #If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ class $X$, then <math>A</math> cannot be harder than $X$, because we can always do a reduction from <math>A</math> to <math>B</math> and solve <math>B</math> instead of directly solving <math>A</math>. |
| | + | |
| | + | #If <math>A</math> is reduced to <math>B</math> and <math>A</math> $\in$ class $X$, then <math>B</math> 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 NP-Hard - just reduce some known NP-Hard problem to this problem |
| | | | |
| | Assume all reductions are done in polynomial time | | Assume all reductions are done in polynomial time |
| Line 5: |
Line 15: |
| | Consider problems $A$, $B$ and $C$ | | Consider problems $A$, $B$ and $C$ |
| | | | |
| − | *If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ class $X$, then <math>A</math> cannot be harder than $X$, because we can always do a reduction from <math>A</math> to <math>B</math> and solve <math>B</math> instead of directly solving <math>A</math>.
| + | |
| | | | |
| | ===Somethings to take care of=== | | ===Somethings to take care of=== |
| Line 12: |
Line 22: |
| | *If <math>A</math> is reduced to <math>B</math>, <math>C</math> is reduced to <math>A</math> , <math>B \in NP </math> and $C \in$ <math>NPC</math>, then <math>A</math> $\in$ <math>NPC</math> | | *If <math>A</math> is reduced to <math>B</math>, <math>C</math> is reduced to <math>A</math> , <math>B \in NP </math> and $C \in$ <math>NPC</math>, then <math>A</math> $\in$ <math>NPC</math> |
| | **Here, the first reduction says that <math>A</math> is in <math>NP</math>. The second reduction says that all <math>NP</math> problems can be reduced to <math>A</math>. Hence, the two sufficient conditions for <math>NPC</math> are complete and hence <math>A</math> is in <math>NPC</math> | | **Here, the first reduction says that <math>A</math> is in <math>NP</math>. The second reduction says that all <math>NP</math> problems can be reduced to <math>A</math>. Hence, the two sufficient conditions for <math>NPC</math> are complete and hence <math>A</math> is in <math>NPC</math> |
| − | *If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ NPH, then <math>A</math> $\in$ <math>?</math> | + | *If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ NP-Hard, then <math>A</math> $\in$ <math>?</math> |
| − | **Here we can't say anything about <math>A</math>. It can be as hard as <math>NPH</math>, or as simple as <math>P</math> | + | **Here we can't say anything about <math>A</math>. It can be as hard as <math>NP-Hard</math>, or as simple as <math>P</math> |
| | | | |
| | | | |
Reducing a problem A to problem B means converting an instance of problem A to problem B. Then, if we know the solution of problem B, we can solve problem A.
Consider the following example:
You want to go from Bangalore to Delhi and you have a ticket from Mumbai to Delhi. So, you get a ticket from Bangalore to Mumbai. So, the problem of going from Bangalore to Delhi got reduced to a problem of going from Mumbai to Delhi.
GATECSE