Difference between revisions of "Some Reduction Inferences"

Line 7: Line 7:
 
*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$ 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> 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> and <math>C</math> is reduced to <math>A</math> and <math>B, C</math> $\in$ NPC, then <math>A</math> $\in$ <math>NPC</math>  
+
*If <math>A</math> is reduced to <math>B</math>, <math>C</math> is reduced to <math>A</math> , <math>B \in NPC </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>
 
*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
 
Here we can't say anything about A. It can be as hard as NPH, or as simple as P
−
*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>
 

Revision as of 12:32, 30 December 2013

Assume all reductions are done in polynomial time

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

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 NPC </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

Retrieved from "https://gatecse.in/w/index.php?title=Some_Reduction_Inferences&oldid=2065"

Assume all reductions are done in polynomial time

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

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> and <math>C</math> is reduced to <math>A</math> and <math>B, C</math> $\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

  • 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>