Difference between revisions of "Some Reduction Inferences"

(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>
Retrieved from "https://gatecse.in/w/index.php?title=Some_Reduction_Inferences&oldid=2057"

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>