It might be because of the name but many graduate students find it difficult to understand $NP$ 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)
$P$ Problems
As the name says these problems can be solved in polynomial time, i.e.; $O(n)$, $O(n^2)$ or $O(n^k)$, where $k$ is a constant.
$NP$ Problems
Some think $NP$ 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 $P$ but in $NP$ is Integer Factorization.
$NP$ Complete Problems$(NPC)$
Over the years many problems in $NP$ have been proved to be in $P$ (like Primality Testing). Still, there are many problems in $NP$ not proved to be in $P$. i.e.; the question still remains whether $P = NP$ (i.e.; whether all $NP$ problems are actually $P$ problems).
$NP$ Complete Problems helps in solving the above question. They are a subset of $NP$ problems with the property that all other $NP$ problems can be reduced to any of them in polynomial time. So, they are the hardest problems in $NP$, in terms of running time. If it can be showed that any $NPC$ Problem is in $P$, then all problems in $NP$ will be in $P$ (because of $NPC$ definition), and hence $P = NP = NPC$.
All $NPC$ problems are in $NP$ (again, due to $NPC$ definition). Examples of $NPC$ problems
$NP$ Hard Problems $(NPH)$
These problems need not have any bound on their running time. If any $NPC$ Problem is polynomial time reducible to a problem $X$, that problem $X$ belongs to $NP$ Hard class. Hence, all $NP$ Complete problems are also $NPH$. In other words if a $NPH$ problem is non-deterministic polynomial time solvable, it is a $NPC$ problem. Example of a $NP$ problem that is not $NPC$ is Halting Problem.
From the diagram, its clear that $NPC$ problems are the hardest problems in $NP$ while being the simplest ones in $NPH$. i.e.; $NP ∩ NPH = NPC$
Note
Given a general problem, we can say its in $NPC$, if and only if we can reduce it to some $NP$ problem (which shows it is in NP) and also some $NPC$ problem can be reduced to it (which shows all NP problems can be reduced to this problem).
Also, if a $NPH$ problem is in $NP$, then it is $NPC$
8,995 total views, 16 views today