Some Reduction Inferences Revision as of 12:23, 30 December 2013 by Arjun Suresh (talk | contribs) (diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Assume all reductions are done in polynomial time

$P \subseteq NP \subseteq NPC \subseteq 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> (<math>B</math> may also be in <math>P</math>, but <math>P</math> <math>\subseteq</math> <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$ NPH, 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>