(Created page with "Assume all reductions are done in polynomial time *If problem A is reduced to a problem B and B $\in$ P, then A $\in$ P")
 
Line 1: Line 1:
 
Assume all reductions are done in polynomial time
 
Assume all reductions are done in polynomial time
*If problem A is reduced to a problem B and B $\in$ P, then A $\in$ P
+
*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>

Revision as of 12:15, 30 December 2013

Assume all reductions are done in polynomial time

  • 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

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