|
We saw earlier that a problem Z is m-complete if
Z is partially computable, and
for every partially computable set X, X ≤m Z.
Intuitively, that means that Z is among the hardest of the partially computable problems.
Now we use the same idea to identify problems that are among the hardest problems in NP. But we need to use polynomial time reductions.
Definition. A language S is NP-complete if both of the following are true.
S is in NP.
For every language X in NP, X ≤p S.
Intuitively, an NP-complete problem is among the hardest problems in NP.
You would expect that an NP-complete problem is not in P.
We don't know that yet, but it is easy to show the following.
Theorem.
Suppose that P ≠ NP.
If S is NP-complete then
S is not in P.
Proof. We know that P ⊆ NP.
Since we are supposing that P ≠ NP, there must exist a language Z that is in NP but not in P.
Since S is assumed to be NP-complete, X ≤p S every problem X in NP.
In particular, since Z is in NP, Z ≤p S.
We are trying to show that S is not in P. Reasoning by contradiction, suppose that S is in P.
Then Z ≤p S and S ∈ P. By the fundamental theorem of polynomial time reductions, Z is also in P.
But that contradicts the fact that Z was chosen not to be in P. ◊
|