P, NP, NP-Complete, NP-Hard

It might be because of the name but many graduate students find it difficult to understand $\textsf{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)

$\textsf{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.

$\textsf{NP}$ Problems

Some think $\text{NP}$ as Non-Polynomial. But actually it is Non-deterministic Polynomial time. i.e.; “yes/no” 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 by a deterministic Turing machine (or equivalently our computer). Examples include all $\textsf{P}$ problems. One example of a problem not in $\text{P}$ but in $\text{NP}$ is Integer Factorization.

$\textsf{NP}$ Complete Problems$(\textsf{NPC})$

Over the years many problems in $\textsf{NP}$ have been proved to be in $\textsf{P}$ (like Primality Testing). Still, there are many problems in $\textsf{NP}$ not proved to be in $\textsf{P}$. i.e.; the question still remains whether $\textsf{P} = \textsf{NP}$ (i.e.; whether all $\textsf{NP}$ problems are actually $\textsf{P}$ problems).

$\textsf{NP}$ Complete Problems helps in solving the above question. They are a subset of $\textsf{NP}$ problems with the property that all other $\textsf{NP}$ problems can be reduced to any of them in polynomial time. So, they are the hardest problems in $\textsf{NP}$, in terms of running time. If it can be showed that any $\textsf{NPC}$ Problem is in $\textsf{P}$, then all problems in $\textsf{NP}$ will be in $\textsf{P}$ (because of $\textsf{NPC}$ definition), and hence $\textsf{P} =\textsf{NP} = \textsf{NPC}$.

All $\textsf{NPC}$ problems are in $\textsf{NP}$ (again, due to $\textsf{NPC}$ definition). Examples of $NPC$ problems

$\textsf{NP}$ Hard Problems $(\textsf{NPH})$

These problems need not have any bound on their running time. If any $\textsf{NPC}$ Problem is polynomial time reducible to a problem $X$, that problem $X$ belongs to $\textsf{NP-Hard}$ class. Hence, all $\textsf{NP-Complete}$ problems are also $\textsf{NPH}$. In other words if a $\textsf{NPH}$ problem is non-deterministic polynomial time solvable, it is a $\textsf{NPC}$ problem. Example of a $\textsf{NPH}$ problem that is not $\textsf{NPC}$ is Halting Problem (halting problem is undecidable and all undecidable problem is guaranteed not to be in $\textsf{NP}$ and hence not $\textsf{NPC}$ also).

From the diagram, it is clear that $\textsf{NPC}$ problems are the hardest problems in $\textsf{NP}$ while being the simplest ones in $\textsf{NPH}$. i.e.; $\textsf{NP} ∩ \textsf{NPH} = \textsf{NPC}$

Note

Given a general problem, we can say it is in $\textsf{NPC}$, if and only if we can reduce it to some $\textsf{NP}$ problem (which shows it is in $\textsf{NP}$) and also some $\textsf{NPC}$ problem can be reduced to it (which shows all $\textsf{NP}$ problems can be reduced to this problem).

Also, if a $\textsf{NPH}$ problem is in $\textsf{NP}$, then it is $\textsf{NPC}$

Some Reduction Inferences