(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
$P \subseteq NP \subseteq NPC \subseteq NPH$
+
<metadesc>Reduction to|from P, NP, NPC and NP-Hard problems</metadesc>
  
 
[[NP,_NP_Complete,_NP_Hard | P, NP, NPC, NPH]]
 
[[NP,_NP_Complete,_NP_Hard | P, NP, NPC, NPH]]
 +
 +
*<math>P</math> is a subset of <math>NP</math>, but whether <math>P = NP</math> is  still not known
 +
*<math>NPC</math> is a subset of <math>NP</math> (only if <math>P \neq NP</math>, <math>NPC</math> is a proper subset of <math>NP</math>)
 +
*<math>NPC</math> is a proper subset of <math>NPH</math>
 +
 
==Reduction==
 
==Reduction==
 
Reducing a problem <math>A</math> to problem <math>B</math> means converting an instance of problem <math>A</math> to an instance of problem <math>B</math>. Then, if we know the solution of problem <math>B</math>, we can solve problem <math>A</math> by using it.  
 
Reducing a problem <math>A</math> to problem <math>B</math> means converting an instance of problem <math>A</math> to an instance of problem <math>B</math>. Then, if we know the solution of problem <math>B</math>, we can solve problem <math>A</math> by using it.  
Line 20: Line 25:
 
**Here, we cannot say <math>A</math> is <math>NPC</math>. All we can say is <math>A</math> cannot be harder than <math>NPC</math> and hence <math>NP</math> (all <math>NPC</math> problems are in <math>NP</math>). To belong to <math>NPC</math>, all <math>NP</math> problems must be reducible to <math>A</math>, which we cannot guarantee from the given statement.
 
**Here, we cannot say <math>A</math> is <math>NPC</math>. All we can say is <math>A</math> cannot be harder than <math>NPC</math> and hence <math>NP</math> (all <math>NPC</math> problems are in <math>NP</math>). To belong to <math>NPC</math>, all <math>NP</math> problems must be reducible to <math>A</math>, which we cannot guarantee 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$ <math>NPC</math>, 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 NP </math> and  $C \in$ <math>NPC</math>, then <math>A</math> $\in$ <math>NPC</math>  
**Here, the first reduction says that <math>A</math> is in <math>NP</math>. The second reduction says that all <math>NP</math> problems can be reduced to <math>A</math>. Hence, the two sufficient conditions for <math>NPC</math> are satisfied and <math>A</math> is in <math>NPC</math>
+
**Here, the first reduction says that <math>A</math> is in <math>NP</math>. The second reduction says that all <math>NP</math> problems can be reduced to <math>A</math> (because <math>C</math> is in <math>NPC</math>, by definition of <math>NPC</math>, all problems in <math>NP</math> are reducible to <math>C</math> and now <math>C</math> is reduced to <math>A</math>). Hence, the two necessary and sufficient conditions for <math>NPC</math> are satisfied and <math>A</math> is 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 <math>A</math>. It can be as hard as <math>NPH</math>, or as simple as <math>P</math>.
 
**Here we can't say anything about <math>A</math>. It can be as hard as <math>NPH</math>, or as simple as <math>P</math>.
Line 28: Line 33:
  
  
 +
[[Category: Automata Theory Notes]]
  
[[Category: Automata Theory]]
+
[[Category: Compact Notes for Reference of Understanding]]
 
 
[[Category:Notes & Ebooks for GATE Preparation]]
 

Latest revision as of 09:47, 14 July 2014


P, NP, NPC, NPH

  • <math>P</math> is a subset of <math>NP</math>, but whether <math>P = NP</math> is still not known
  • <math>NPC</math> is a subset of <math>NP</math> (only if <math>P \neq NP</math>, <math>NPC</math> is a proper subset of <math>NP</math>)
  • <math>NPC</math> is a proper subset of <math>NPH</math>

Reduction

Reducing a problem <math>A</math> to problem <math>B</math> means converting an instance of problem <math>A</math> to an instance of problem <math>B</math>. Then, if we know the solution of problem <math>B</math>, we can solve problem <math>A</math> by using it.

Consider the following example:

You want to go from Bangalore to Delhi and you can get a ticket from Mumbai to Delhi. So, you ask your friend for a lift from Bangalore to Mumbai. So, the problem of going from Bangalore to Delhi got reduced to a problem of going from Mumbai to Delhi.

Some Inferences

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

Assume all reductions are done in polynomial time

2 Important Points

  1. 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 directly solving <math>A</math>. This reduction thus gives an upper bound for the complexity of <math>A</math>.
  2. If <math>A</math> is reduced to <math>B</math> and <math>A</math> $\in$ class $X$, then <math>B</math> cannot be easier than $X$. The argument is exactly same as for the one above. This reduction is used to show if a problem belongs to <math>NPH</math> - just reduce some known <math>NPH</math> problem to the given problem. This reduction thus gives a lower bound for the complexity of <math>B</math>.

Somethings to take care of

  • If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ <math>NPC</math>, then <math>A</math> $\in$ <math>NP</math>
    • Here, we cannot say <math>A</math> is <math>NPC</math>. All we can say is <math>A</math> cannot be harder than <math>NPC</math> and hence <math>NP</math> (all <math>NPC</math> problems are in <math>NP</math>). To belong to <math>NPC</math>, all <math>NP</math> problems must be reducible to <math>A</math>, which we cannot guarantee 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$ <math>NPC</math>, then <math>A</math> $\in$ <math>NPC</math>
    • Here, the first reduction says that <math>A</math> is in <math>NP</math>. The second reduction says that all <math>NP</math> problems can be reduced to <math>A</math> (because <math>C</math> is in <math>NPC</math>, by definition of <math>NPC</math>, all problems in <math>NP</math> are reducible to <math>C</math> and now <math>C</math> is reduced to <math>A</math>). Hence, the two necessary and sufficient conditions for <math>NPC</math> are satisfied and <math>A</math> is 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 <math>A</math>. It can be as hard as <math>NPH</math>, or as simple as <math>P</math>.




blog comments powered by Disqus

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

P, NP, NPC, NPH

Reduction[edit]

Reducing a problem <math>A</math> to problem <math>B</math> means converting an instance of problem <math>A</math> to an instance of problem <math>B</math>. Then, if we know the solution of problem <math>B</math>, we can solve problem <math>A</math> by using it.

Consider the following example:[edit]

You want to go from Bangalore to Delhi and you can get a ticket from Mumbai to Delhi. So, you ask your friend for a lift from Bangalore to Mumbai. So, the problem of going from Bangalore to Delhi got reduced to a problem of going from Mumbai to Delhi.

Some Inferences[edit]

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

Assume all reductions are done in polynomial time

2 Important Points[edit]

  1. 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 directly solving <math>A</math>. This reduction thus gives an upper bound for the complexity of <math>A</math>.
  2. If <math>A</math> is reduced to <math>B</math> and <math>A</math> $\in$ class $X$, then <math>B</math> cannot be easier than $X$. The argument is exactly same as for the one above. This reduction is used to show if a problem belongs to <math>NPH</math> - just reduce some known <math>NPH</math> problem to the given problem. This reduction thus gives a lower bound for the complexity of <math>B</math>.

Somethings to take care of[edit]




blog comments powered by Disqus