Difference between revisions of "Some Reduction Inferences"

Revision as of 12:20, 30 December 2013

Assume all reductions are done in polynomial time

$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$ 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$ 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$ 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>

@@ Line 1: / Line 1: @@
 Assume all reductions are done in polynomial time
-$P \le NP \le NPC \le 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$ NP, then <math>A</math> $\in$ <math>NP</math>