View source for Some Reduction Inferences ← Some Reduction Inferences

You do not have permission to edit this page, for the following reason:

The action you have requested is limited to users in one of the groups: Users, Administrators.

You can view and copy the source of this page.

Templates used on this page:

Return to Some Reduction Inferences.

Retrieved from "https://gatecse.in/wiki/Some_Reduction_Inferences"

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>