Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 3: | Line 3: | ||
$P \subseteq NP \subseteq NPC \subseteq NPH$ | $P \subseteq NP \subseteq NPC \subseteq NPH$ | ||
*If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ P, then <math>A</math> $\in$ <math>P</math> | *If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ P, then <math>A</math> $\in$ <math>P</math> | ||
| − | *If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ NP, then <math>A</math> $\in$ <math>NP</math> | + | *If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ NP, then <math>A</math> $\in$ <math>NP</math> (<math>B</math> may also be in <math>P</math>, but <math>P</math> \subseteq <math>NP</math>) |
*If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ NPC, then <math>A</math> $\in$ <math>NP</math> | *If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ NPC, then <math>A</math> $\in$ <math>NP</math> | ||
| − | *If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ | + | *If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ NPH, then <math>A</math> $\in$ <math>P</math> |
*If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ P, then <math>A</math> $\in$ <math>P</math> | *If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ P, then <math>A</math> $\in$ <math>P</math> | ||
*If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ P, then <math>A</math> $\in$ <math>P</math> | *If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ P, then <math>A</math> $\in$ <math>P</math> | ||
*If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ P, then <math>A</math> $\in$ <math>P</math> | *If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ P, then <math>A</math> $\in$ <math>P</math> | ||
*If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ P, then <math>A</math> $\in$ <math>P</math> | *If problem <math>A</math> is reduced to a problem <math>B</math> and <math>B</math> $\in$ P, then <math>A</math> $\in$ <math>P</math> | ||
Assume all reductions are done in polynomial time
$P \subseteq NP \subseteq NPC \subseteq NPH$
Assume all reductions are done in polynomial time
$P \subseteq NP \subseteq NPC \subseteq NPH$
GATECSE