Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 10: | Line 10: | ||
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 [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. 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>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). | 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). | ||
<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>NP</math> Complete Problem is in <math>P</math>, then all problems in <math>NP</math> will be in <math>P</math> (because of <math>NP</math> Complete definition), and hence <math>P = NP = NPC</math>. | <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>NP</math> Complete Problem is in <math>P</math>, then all problems in <math>NP</math> will be in <math>P</math> (because of <math>NP</math> Complete definition), and hence <math>P = NP = NPC</math>. | ||
| − | All <math> | + | All <math>NPC</math> problems are in <math>NP</math> (again, due to <math>NP</math> Complete definition). Examples of [https://en.wikipedia.org/wiki/List_of_NP-complete_problems <math>NP</math> Complete problems] |
| − | ==<math>NP</math> Hard Problems== | + | ==<math>NP</math> Hard Problems <math>(NPH)</math>== |
| − | These problems need not have any bound on their running time. If any <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]. |
| Line 24: | Line 24: | ||
| − | From the diagram, its clear that <math>NPC</math> are the hardest problems in <math>NP</math> while being the simplest ones in <math> | + | 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>. |
--[[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) | ||
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)
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.
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.
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>NP</math> Complete Problem is in <math>P</math>, then all problems in <math>NP</math> will be in <math>P</math> (because of <math>NP</math> Complete definition), and hence <math>P = NP = NPC</math>.
All <math>NPC</math> problems are in <math>NP</math> (again, due to <math>NP</math> Complete definition). Examples of <math>NP</math> Complete problems
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.
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>.
--Arjun (talk) 22:48, 16 November 2013 (UTC)
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)
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.
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.
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>NP</math> Complete Problem is in <math>P</math>, then all problems in <math>NP</math> will be in <math>P</math> (because of <math>NP</math> Complete definition), and hence <math>P = NP = NPC</math>.
All <math>NP</math> Complete problems are in <math>NP</math> (again, due to <math>NP</math> Complete definition). Examples of <math>NP</math> Complete problems
These problems need not have any bound on their running time. If any <math>NP</math> Complete 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>NP</math> Hard. In other words if a <math>NP</math> Hard problem is non-deterministic polynomial time solvable, its a <math>NP</math> Complete problem. Example of a <math>NP</math> Hard problem that's not <math>NP</math> Complete is Halting Problem.
From the diagram, its clear that <math>NPC</math> are the hardest problems in <math>NP</math> while being the simplest ones in <math>NP</math> Hard
--Arjun (talk) 22:48, 16 November 2013 (UTC)
GATECSE