Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
Line 3: | Line 3: | ||
[[NP,_NP_Complete,_NP_Hard | P, NP, NPC, NPH]] | [[NP,_NP_Complete,_NP_Hard | P, NP, NPC, NPH]] | ||
− | *<math>P</math> is a subset of <math>NP</math>, but whether <math>P = NP</math> is still not known | + | *<math>P</math> is a subset of <math>NP</math>, but whether <math>P = NP</math> is still not known |
*<math>NPC</math> is a subset of <math>NP</math> (only if <math>P \neq NP</math>, <math>NPC</math> is a proper subset of <math>NP</math>) | *<math>NPC</math> is a subset of <math>NP</math> (only if <math>P \neq NP</math>, <math>NPC</math> is a proper subset of <math>NP</math>) | ||
*<math>NPC</math> is a proper subset of <math>NPH</math> | *<math>NPC</math> is a proper subset of <math>NPH</math> |
Reducing a problem <math>A</math> to problem <math>B</math> means converting an instance of problem <math>A</math> to an instance of problem <math>B</math>. Then, if we know the solution of problem <math>B</math>, we can solve problem <math>A</math> by using it.
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.
Consider problems $A$, $B$ and $C$.
Assume all reductions are done in polynomial time
Reducing a problem <math>A</math> to problem <math>B</math> means converting an instance of problem <math>A</math> to an instance of problem <math>B</math>. Then, if we know the solution of problem <math>B</math>, we can solve problem <math>A</math> by using it.
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.
Consider problems $A$, $B$ and $C$.
Assume all reductions are done in polynomial time