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

$P \subseteq NP \subseteq NPC \subseteq NPH$

Assume all reductions are done in polynomial time

Consider problems $A$, $B$ and $C$

• If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ class $X$, then <math>A</math> cannot be harder than $X$, because we can always do a reduction from <math>A</math> to <math>B</math> and solve <math>B</math> instead of <math>A</math>.

Somethings to take care of

• If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ NPC, then <math>A</math> $\in$ <math>NP</math>
  • Here, we cannot say A is NPC. All we can say is A cannot be harder than NPC and hence NP (all NPC problems are in NP). To belong to NPC, all NP problems must be reducible to A, which we cannot tell from the given statement.
• If <math>A</math> is reduced to <math>B</math>, <math>C</math> is reduced to <math>A</math> , <math>B \in NP </math> and $C \in$ NPC, then <math>A</math> $\in$ <math>NPC</math>
  • Here, the first reduction says that A is in NP. The second reduction says that all NP problems can be reduced to A. Hence, the two sufficient conditions for NPC are complete and A is in NPC
• If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ NPH, then <math>A</math> $\in$ <math>?</math>
  • Here we can't say anything about A. It can be as hard as NPH, or as simple as P

Tweet