(NP Complete Problems)
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.
 
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.
  
==<math>P</math> Problems==
+
==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.
 
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.
  
==<math>NP</math> Problem==
+
==NP 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 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].
 
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==
+
==NP Complete Problems==
 
Over 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>.  
 
Over 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>.  
  
Line 14: Line 14:
 
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]
 
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]
  
==<math>NP</math> Hard Problems==
+
==NP Hard Problems==
  
 
[[Category: Algorithms & Data Structures]]
 
[[Category: Algorithms & Data Structures]]

Revision as of 20:20, 16 November 2013

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

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

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.

NP Complete Problems

Over 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

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.

<math>P</math> 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.

<math>NP</math> Problem[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 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]

Over 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

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