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")
(No difference)

Revision as of 12:14, 30 December 2013

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

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