$$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$

$$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$

NP-complete problems

The class $\mathbf{\text{NP}}$ contains both problems that are easy (those in the class $\mathbf{\text{P}}$) as well as problems for which we do not currently know efficient algorithms (but whose solutions are small and easy to check). There is a special class of problems in $\mathbf{\text{NP}}$ called $\mathbf{\text{NP}}$-complete problems. They have the property that if any of them can be solved in polynomial time, then all of them can. In a sense, they are the hardest problems in the class $\mathbf{\text{NP}}$. And there are lots of such problems.

Definition: Polynomial-time computable reduction

A polynomial-time computable reduction from a decision problem $B$ to a decision problem $A$ is a function $R$ from the instances of $B$ to the instances of $A$ such that for each instance $x$ of $B$,

• ​ $R(x)$ can be computed in polynomial-time, and

• ​ $x$ is a “yes” instance of $B$ if and only if $R(x)$ is a “yes” instance of $A$.

Therefore, if we have

• ​ a polynomial time reduction from $B$ to $A$, and

• ​ a polynomial-time algorithm solving $A$,

then we have a polynomial-time algorithm for solving $B$ as well: given an instance $x$ of $B$, compute $R(x)$ and then run the algorithm for $A$ on $R(x)$.

Definition: NP-completeness

A problem $A$ in $\mathbf{\text{NP}}$ is NP-complete if every other problem $B$ in $\mathbf{\text{NP}}$ can be reduced to it with a polynomial-time computable reduction.

Therefore,

• ​ if an $\mathbf{\text{NP}}$-complete problem $A$ can be solved in polynomial time, then all the problems in $\mathbf{\text{NP}}$ can be solved in polynomial time, and thus

• ​ $\mathbf{\text{NP}}$-complete problems are, in a sense, the most difficult ones in $\mathbf{\text{NP}}$.

We do not know whether $\mathbf{\text{NP}}$-complete problems can be solved efficiently or not.

The Cook-Levin Theorem

The fact that $\mathbf{\text{NP}}$-complete problems exist at all was proven by Cook and Levin in 1970’s.

Theorem: Cook 1971, Levin 1973

$\mathsf{\text{sat}}$ (and $\mathsf{\text{3-cnf-sat}}$) is $\mathbf{\text{NP}}$-complete.

Soon after this, Karp [1972] then listed the next 21 $\mathbf{\text{NP}}$-complete problems. Since then, hundreds of problems have been shown $\mathbf{\text{NP}}$-complete. For instance, $\mathsf{\text{traveling salesperson}}$, $\mathsf{\text{generalized Sudokus}}$ etc are all $\mathbf{\text{NP}}$-complete. For incomplete lists, one can see

• ​ Garey and Johnson, 1979: Computers and Intractability: A Guide to the Theory of NP-Completeness, or

• ​ this Wikipedia page.

NP-completeness: significance

Of course, the question of whether $\mathbf{\text{P}}=\mathbf{\text{NP}}$, or can $\mathbf{\text{NP}}$-complete problems be solved in polynomial time, is a very important open problem in computer science. In fact, it is one of the seven (of which six are still open) one million dollar prize Clay Mathematics Institute Millennium Prize problems.

Because there are hundreds of $\mathbf{\text{NP}}$-complete problems, the $\mathbf{\text{P}}=\mathbf{\text{NP}}$ question has practical significance as well. As Christos Papadimitriou says in his book “Computational complexity”:

There is nothing wrong in trying to prove that an $\mathbf{\text{NP}}$-complete problem can be solved in polynomial time. The point is that without an $\mathbf{\text{NP}}$-completeness proof one would be trying the same thing without knowing it!

That is, suppose that you have a new problem for which you should develop an algorithm that is always efficient, i.e. runs in polynomial time. You may end up in trying really hard for very long time, probably without success, if the problem turns out to be $\mathbf{\text{NP}}$-complete or harder. This is because during the last decades, lots of very clever people have tried to develop polynomial-time algorithms for many $\mathbf{\text{NP}}$-complete problems, but no-one has succeeded so far.