Some Reduction Inferences
Revision as of 12:15, 30 December 2013 by Arjun Suresh (talk | contribs)

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>