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

- L is in NP, and
- 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.

*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:

^{k}) | M is a nondeterministic machine and M(x) accepts in k steps}

^{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.

## No comments:

## Post a Comment