|
|
| (23 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| − | $P \subseteq NP \subseteq NPC \subseteq NPH$
| + | <metadesc>Reduction to|from P, NP, NPC and NP-Hard problems</metadesc> |
| | | | |
| − | Assume all reductions are done in polynomial time
| + | [[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>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> |
| | + | |
| | + | ==Reduction== |
| | + | 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. |
| | + | |
| | + | ===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. |
| | | | |
| − | Consider problems $A$, $B$ and $C$ | + | ===Some Inferences=== |
| | + | 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>.
| + | Assume all reductions are done in polynomial time |
| | + | ===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>. This reduction thus gives an upper bound for the complexity of <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 <math>NPH</math> - just reduce some known <math>NPH</math> problem to the given problem. This reduction thus gives a lower bound for the complexity of <math>B</math>. |
| | | | |
| | ===Somethings to take care of=== | | ===Somethings to take care of=== |
| − | *If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ NPC, then <math>A</math> $\in$ <math>NP</math> | + | *If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ <math>NPC</math>, then <math>A</math> $\in$ <math>NP</math> |
| − | **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 tell from the given statement. | + | **Here, we cannot say <math>A</math> is <math>NPC</math>. All we can say is <math>A</math> cannot be harder than <math>NPC</math> and hence <math>NP</math> (all <math>NPC</math> problems are in <math>NP</math>). To belong to <math>NPC</math>, all <math>NP</math> problems must be reducible to <math>A</math>, which we cannot guarantee from the given statement. |
| − | *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$ NPC, 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 A is in NP. The second reduction says that all NP problems can be reduced to A. Hence, the two sufficient conditions for NPC are complete and A is in NPC | + | **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> (because <math>C</math> is in <math>NPC</math>, by definition of <math>NPC</math>, all problems in <math>NP</math> are reducible to <math>C</math> and now <math>C</math> is reduced to <math>A</math>). Hence, the two necessary and sufficient conditions for <math>NPC</math> are satisfied and <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$ $NPH$, then <math>A</math> $\in$ <math>?</math> |
| − | **Here we can't say anything about A. It can be as hard as NPH, or as simple as P | + | **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>. |
| | | | |
| | | | |
| Line 19: |
Line 33: |
| | | | |
| | | | |
| | + | [[Category: Automata Theory Notes]] |
| | | | |
| − | [[Category: Automata Theory]] | + | [[Category: Compact Notes for Reference of Understanding]] |
| − | | |
| − | [[Category:Notes & Ebooks for GATE Preparation]]
| |
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.
GATECSE