Difference between revisions of "NP, NP Complete, NP Hard"

(→‎NP Problems)
 
(127 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 Problems==
+
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>\sigma</math>
 
−
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 and 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].
 
  
−
==<math>NP</math> Complete Problems==
+
==<math>P</math> Problems==
−
$\sigma$
+
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.
−
ver the years many problems in <math>NP</math> have been proved to be in <math>P</math> also (like [https://en.wikipedia.org/wiki/Primality_test Primality Testing]). Still, there are many problems in <math>NP</math> still not proved to be in <math>P</math>. i.e.; the question still remains whether <math>P = NP</math>.  
 
  
−
<math>NP</math> Complete Problems are an aid in solving this 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 <math>NP</math> Complete problem in polynomial time. So, they are the hardest problems in <math>NP</math> in terms of running time. Also, if anyone can show that an <math>NP</math> Complete Problem is in <math>P</math>, then all problems in <math>NP</math> will be in <math>P</math>, and hence <math>P = NP = NPC</math>.
+
==<math>NP</math> Problems==
  
−
All <math>NP</math> Complete problems are in <math>NP</math> because of the definition. Examples of [https://en.wikipedia.org/wiki/List_of_NP-complete_problems <math>NP</math> 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>==
−
These problems need not have any bound on their running time. If any NP Complete Problem is polynomial time reducable to a problem, that problem belongs to NP Hard class. Hence, all NP Complete problems are also NP Hard. In other words if a NP Hard problem is non-deterministic polynomial time solvable, its a NP Complete problem. Example of a NP Hard problem that's not NP Complete is [https://en.wikipedia.org/wiki/Halting_problem Halting Problem].
+
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
Retrieved from "https://gatecse.in/w/index.php?title=NP,_NP_Complete,_NP_Hard&oldid=5351"

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 Problems[edit]

<math>\sigma</math> 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 and one example of a problem not in <math>P</math> but in <math>NP</math> is Integer Factorization.

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

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

<math>NP</math> Complete Problems are an aid in solving this 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 <math>NP</math> Complete problem in polynomial time. So, they are the hardest problems in <math>NP</math> in terms of running time. Also, if anyone can show that an <math>NP</math> Complete Problem is in <math>P</math>, then all problems in <math>NP</math> will be in <math>P</math>, and hence <math>P = NP = NPC</math>.

All <math>NP</math> Complete problems are in <math>NP</math> because of the definition. Examples of <math>NP</math> Complete problems

NP Hard Problems[edit]

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