| 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. | ||
| − | ==P Problems== | + | ==<math>P</math> 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. | ||
| − | ==NP Problem== | + | ==<math>NP</math> Problem== |
| − | 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]. | + | 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]. |
| − | ==NP Complete Problems== | + | ==<math>NP</math> Complete 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>. | + | 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> not been proved to be in <math>P</math>. 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. | + | <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 NP Complete problems are in NP because of the definition. Examples of NP Complete problems | + | All <math>NP</math> Complete problems are in <math>NP</math> because of the definition. Examples of <math>NP</math> Complete problems includes [https://en.wikipedia.org/wiki/List_of_NP-complete_problems <math>NP</math> Complete Problems] |
| − | ==NP Hard Problems== | + | ==<math>NP</math> Hard Problems== |
[[Category: Algorithms & Data Structures]] | [[Category: Algorithms & Data Structures]] | ||
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.
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.
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.
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> not been 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 includes <math>NP</math> Complete 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.
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.
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.
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
GATECSE