Line 25: Line 25:
  
 
From the diagram, its clear that <math>NPC</math> problems are the hardest problems in <math>NP</math> while being the simplest ones in <math>NPH</math>. i.e.;  
 
From the diagram, its clear that <math>NPC</math> problems are the hardest problems in <math>NP</math> while being the simplest ones in <math>NPH</math>. i.e.;  
  $NP ∩ NPH = NPC$
+
  NP ∩ NPH = NPC
  
 
--[[User:Arjun|Arjun]] ([[User talk:Arjun|talk]]) 22:48, 16 November 2013 (UTC)
 
--[[User:Arjun|Arjun]] ([[User talk:Arjun|talk]]) 22:48, 16 November 2013 (UTC)

Revision as of 19:14, 20 December 2013


It might be because of the name but many graduate students find it difficult to understand <math>NP</math> problems. So, I thought of explaining them in an easy way. (When explanation becomes simple, some points may be lost. So, please do refer standard text books for more information)

<math>P</math> Problems

As the name says these problems can be solved in polynomial time, i.e.; <math>O(n)</math>, <math>O(n^2)</math> or <math>O(n^k)</math>, where <math>k</math> is a constant.

<math>NP</math> Problems

Some think <math>NP</math> as Non-Polynomial. But actually its Non-deterministic Polynomial time. i.e.; these problems can be solved in polynomial time by a non-deterministic Turing machine and hence in exponential time by a deterministic Turing machine. In other words these problems can be verified (if a solution is given, say if its correct or wrong) in polynomial time. Examples include all P problems. One example of a problem not in <math>P</math> but in <math>NP</math> is Integer Factorization.

<math>NP</math> Complete Problems<math>(NPC)</math>

Over the years many problems in <math>NP</math> have been proved to be in <math>P</math> (like Primality Testing). Still, there are many problems in <math>NP</math> not proved to be in <math>P</math>. i.e.; the question still remains whether <math>P = NP</math> (i.e.; whether all <math>NP</math> problems are actually <math>P</math> problems).

<math>NP</math> Complete Problems helps in solving the above question. They are a subset of <math>NP</math> problems with the property that all other <math>NP</math> problems can be reduced to any of them in polynomial time. So, they are the hardest problems in <math>NP</math>, in terms of running time. If it can be showed that any <math>NPC</math> Problem is in <math>P</math>, then all problems in <math>NP</math> will be in <math>P</math> (because of <math>NPC</math> definition), and hence <math>P = NP = NPC</math>.

All <math>NPC</math> problems are in <math>NP</math> (again, due to <math>NPC</math> definition). Examples of <math>NPC</math> problems

<math>NP</math> Hard Problems <math>(NPH)</math>

These problems need not have any bound on their running time. If any <math>NPC</math> Problem is polynomial time reducible to a problem <math>X</math>, that problem <math>X</math> belongs to <math>NP</math> Hard class. Hence, all <math>NP</math> Complete problems are also <math>NPH</math>. In other words if a <math>NPH</math> problem is non-deterministic polynomial time solvable, its a <math>NPC</math> problem. Example of a <math>NP</math> problem that's not <math>NPC</math> is Halting Problem.


800px-P_np_np-complete_np-hard.svg.png


From the diagram, its clear that <math>NPC</math> problems are the hardest problems in <math>NP</math> while being the simplest ones in <math>NPH</math>. i.e.;

NP ∩ NPH = NPC

--Arjun (talk) 22:48, 16 November 2013 (UTC)




blog comments powered by Disqus


It might be because of the name but many graduate students find it difficult to understand <math>NP</math> problems. So, I thought of explaining them in an easy way. (When explanation becomes simple, some points may be lost. So, please do refer standard text books for more information)

<math>P</math> Problems[edit]

As the name says these problems can be solved in polynomial time, i.e.; <math>O(n)</math>, <math>O(n^2)</math> or <math>O(n^k)</math>, where <math>k</math> is a constant.

<math>NP</math> Problems[edit]

Some think <math>NP</math> as Non-Polynomial. But actually its Non-deterministic Polynomial time. i.e.; these problems can be solved in polynomial time by a non-deterministic Turing machine and hence in exponential time by a deterministic Turing machine. In other words these problems can be verified (if a solution is given, say if its correct or wrong) in polynomial time. Examples include all P problems. One example of a problem not in <math>P</math> but in <math>NP</math> is Integer Factorization.

<math>NP</math> Complete Problems<math>(NPC)</math>[edit]

Over the years many problems in <math>NP</math> have been proved to be in <math>P</math> (like Primality Testing). Still, there are many problems in <math>NP</math> not proved to be in <math>P</math>. i.e.; the question still remains whether <math>P = NP</math> (i.e.; whether all <math>NP</math> problems are actually <math>P</math> problems).

<math>NP</math> Complete Problems helps in solving the above question. They are a subset of <math>NP</math> problems with the property that all other <math>NP</math> problems can be reduced to any of them in polynomial time. So, they are the hardest problems in <math>NP</math>, in terms of running time. If it can be showed that any <math>NPC</math> Problem is in <math>P</math>, then all problems in <math>NP</math> will be in <math>P</math> (because of <math>NPC</math> definition), and hence <math>P = NP = NPC</math>.

All <math>NPC</math> problems are in <math>NP</math> (again, due to <math>NPC</math> definition). Examples of <math>NPC</math> problems

<math>NP</math> Hard Problems <math>(NPH)</math>[edit]

These problems need not have any bound on their running time. If any <math>NPC</math> Problem is polynomial time reducible to a problem <math>X</math>, that problem <math>X</math> belongs to <math>NP</math> Hard class. Hence, all <math>NP</math> Complete problems are also <math>NPH</math>. In other words if a <math>NPH</math> problem is non-deterministic polynomial time solvable, its a <math>NPC</math> problem. Example of a <math>NP</math> problem that's not <math>NPC</math> is Halting Problem.


800px-P_np_np-complete_np-hard.svg.png


From the diagram, its clear that <math>NPC</math> problems are the hardest problems in <math>NP</math> while being the simplest ones in <math>NPH</math>. i.e.;

NP ∩ NPH = NPC

--Arjun (talk) 22:48, 16 November 2013 (UTC)




blog comments powered by Disqus