|
|
| Line 1: |
Line 1: |
| | + | $P \subseteq NP \subseteq NPC \subseteq NPH$ |
| | + | |
| | Assume all reductions are done in polynomial time | | Assume all reductions are done in polynomial time |
| − |
| |
| − | $P \subseteq NP \subseteq NPC \subseteq NPH$
| |
| | | | |
| | Consider problems $A$, $B$ and $C$ | | Consider problems $A$, $B$ and $C$ |
Revision as of 12:57, 30 December 2013
$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$ P, then <math>A</math> $\in$ <math>P</math>
- If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ NP, then <math>A</math> $\in$ <math>NP</math>
- (<math>A</math> may also be in <math>P</math>, but that cannot be inferred from the given statement)
- If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ NPC, then <math>A</math> $\in$ <math>NP</math>
- (<math>A</math> may also be in <math>NPC</math>, but that cannot be inferred 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>
- 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
GATECSE