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
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,1k) | M is a nondeterministic machine
and M(x) accepts in k steps}
Here 1k 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,1p(|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.
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.
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 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,1p(|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