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.

$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[edit]

  • 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




blog comments powered by Disqus