(NP Problems)
 
(142 intermediate revisions by 3 users not shown)
Line 1: Line 1:
It might be because of the name that many graduate students find it difficult to understand about NP problems. So, I thought of explaining them as easy as I can.
+
<metadesc>NP Complete definition in simple terms. Differences between P, NP, NP Complete and NP Hard Problems</metadesc>
  
==P Problems==
 
As the name says these problems can be solved in polynomial time, i.e.; <math>O(n), O(n^2) or O(n^k), </math>where <math>k</math> is a constant.
 
  
==NP Problem==
+
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)
Some think NP 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 and one example of a problem not in P but in NP is [https://en.wikipedia.org/wiki/Integer_factorization_problem Integer Factorization].
 
  
==NP Complete Problems==
+
==<math>P</math> Problems==
Over the years many problems in NP have been proved to be in P also (like [https://en.wikipedia.org/wiki/Primality_test Primality Testing]). Still, there are many problems in NP not been proved to be in P. i.e.; the question still remains whether <math>P = NP</math>.  
+
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.
  
NP Complete Problems are an aid in solving this question. They are a subset of NP problems with the property that all other NP problems can be reduced to any NP Complete problem in polynomial time. So, they are the hardest problems in NP in terms of running time. Also, if anyone can show that an NP Complete Problem is in P, then all problems in NP will be in P, and hence P = NP = NPC.
+
==<math>NP</math> Problems==
  
All NP Complete problems are in NP because of the definition. Examples of NP Complete problems include [https://en.wikipedia.org/wiki/List_of_NP-complete_problems NP Complete Problems]
+
Some think <math>NP</math> as Non-Polynomial. But actually it is [https://en.wikipedia.org/wiki/NP_(complexity) Non-deterministic Polynomial time]. i.e.; "yes" instances of these problems can be solved in polynomial time by a non-deterministic Turing machine and hence can take up to exponential time (some problems can be solved in sub-exponential but super polynomial time) by a deterministic Turing machine. In other words these problems can be verified (if a solution is given, say if it is 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 [https://en.wikipedia.org/wiki/Integer_factorization_problem Integer Factorization].
  
==NP Hard Problems==
+
==<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 [https://en.wikipedia.org/wiki/Primality_test 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).
  
[[Category: Algorithms & Data Structures]]
+
<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 [https://en.wikipedia.org/wiki/List_of_NP-complete_problems <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 [https://en.wikipedia.org/wiki/Halting_problem Halting Problem].
 +
 
 +
 
 +
https://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/400px-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$
 +
 
 +
===Note===
 +
Given a general problem, we can say its in <math>NPC</math>, if and only if we can reduce it to some <math>NP</math> problem (which shows its in NP) and also some <math>NPC</math> problem can be reduced to it (which shows all NP problems can be reduced to this problem).
 +
 
 +
Also, if a <math>NPH</math> problem is in <math>NP</math>, then it's <math>NPC</math>
 +
 
 +
[[Some Reduction Inferences|Some Reduction Inferences ]]
 +
 
 +
--[[User:Arjun|Arjun]] ([[User talk:Arjun|talk]]) 22:48, 16 November 2013 (UTC)
 +
 
 +
{{Template:FBD}}
 +
 
 +
 
 +
[[Category: Automata Theory Notes]]
 +
 
 +
 
 +
[[Category: Compact Notes for Reference of Understanding]]

Latest revision as of 16:40, 17 September 2015


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 it is Non-deterministic Polynomial time. i.e.; "yes" instances of these problems can be solved in polynomial time by a non-deterministic Turing machine and hence can take up to exponential time (some problems can be solved in sub-exponential but super polynomial time) by a deterministic Turing machine. In other words these problems can be verified (if a solution is given, say if it is 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.


400px-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$

Note

Given a general problem, we can say its in <math>NPC</math>, if and only if we can reduce it to some <math>NP</math> problem (which shows its in NP) and also some <math>NPC</math> problem can be reduced to it (which shows all NP problems can be reduced to this problem).

Also, if a <math>NPH</math> problem is in <math>NP</math>, then it's <math>NPC</math>

Some Reduction Inferences

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




blog comments powered by Disqus

It might be because of the name that many graduate students find it difficult to understand about NP problems. So, I thought of explaining them as easy as I can.

P Problems[edit]

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

NP Problem[edit]

Some think NP 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 and one example of a problem not in P but in NP is Integer Factorization.

NP Complete Problems[edit]

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

NP Complete Problems are an aid in solving this question. They are a subset of NP problems with the property that all other NP problems can be reduced to any NP Complete problem in polynomial time. So, they are the hardest problems in NP in terms of running time. Also, if anyone can show that an NP Complete Problem is in P, then all problems in NP will be in P, and hence P = NP = NPC.

All NP Complete problems are in NP because of the definition. Examples of NP Complete problems include NP Complete Problems

NP Hard Problems[edit]