Line 1: Line 1:
 
Assume all reductions are done in polynomial time
 
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$ 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>

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>

Assume all reductions are done in polynomial time $P \le NP \le NPC \le 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>