Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
Line 5: | Line 5: | ||
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$ P, then <math>A</math> $\in$ <math>P</math> | *If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ P, then <math>A</math> $\in$ <math>P</math> | ||
− | *If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ NP, then <math>A</math> $\in$ <math>NP</math> (<math>A</math> may also be in <math>P</math>, but that cannot be inferred from the given statement) | + | *If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ NP, 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> (<math>A</math> may also be in <math>NPC</math>, but that cannot be inferred from the given statement) | + | **(<math>A</math> may also be in <math>P</math>, but that cannot be inferred from the given statement) |
+ | *If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ NPC, then <math>A</math> $\in$ <math>NP</math> | ||
+ | ** (<math>A</math> may also be in <math>NPC</math>, but that cannot be inferred 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$ NPC, then <math>A</math> $\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> |
Assume all reductions are done in polynomial time
$P \subseteq NP \subseteq NPC \subseteq NPH$
Consider problems $A$, $B$ and $C$
Assume all reductions are done in polynomial time
$P \subseteq NP \subseteq NPC \subseteq NPH$
Consider problems $A$, $B$ and $C$