Foundations of Complexity Lesson 11: NP-Completeness

Previous Lesson | Next Lesson

Informally, NP-complete sets are the hardest sets in NP. What does it mean to be hardest? Here we use a polynomial-time version of reduction, a concept we first saw in Lesson 5.

Formally a language L is NP-complete if

1. L is in NP, and
2. For all A in NP, there is a polynomial-time computable function f such that x is in A if and only if f(x) is in L.

We say that f polynomial-time reduces A to L.

The following theorem captures the intuition for NP-completeness.
Theorem: Let L be an NP-complete language. Then L is in P if and only if P = NP.

Proof: If P = NP then since L is in NP then L is in P. Suppose L is in P and A is in NP. Let f be the reduction from A to L. We can then determine whether x is in A by testing whether f(x) is in L. ◊

In particular if any NP-complete set has an efficient algorithm then all NP-complete sets have efficient algorithms.

Do there exist NP-complete sets? Here is an example:

L = {(<M>,x,1^k) | M is a nondeterministic machine and M(x) accepts in k steps} Here 1^k is just a string consisting of exactly k 1's.

L is in NP by just simulating M(x) for k steps. If A is in NP, then A must be accepted by some nondeterministic machine M using time p(|x|) for some polynomial p. The reduction f is just f(x)=(<M>,x,1^p(|x|)).

L is not a natural language; you are unlikely to see it come up in any real-world application. In future lessons we will see that a large number of truly natural search problems are NP-complete which is why NP-completeness is perhaps the single most important concept to come out of theoretical computer science.