|
|
| Line 9: |
Line 9: |
| | ===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$ NPC, 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>. 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$ 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> |
| | | | |
| | | | |
Revision as of 16:14, 31 December 2013
$P \subseteq NP \subseteq NPC \subseteq NPH$
Assume all reductions are done in polynomial time
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
- If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ NPC, then <math>A</math> $\in$ <math>NP</math>
- 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$ <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>
- 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 <math>A</math>. It can be as hard as <math>NPH</math>, or as simple as <math>P</math>
GATECSE