-
Title:
SAT is NP-Hard - Intro to Algorithms
-
Description:
-
I mentioned NP hardness before.
-
Now that we've talked about reduction, we can revisit that definition and say--
-
a problem X is NP hard if we can reduce some other NP hard problem to it,
-
what that really means is we can use a solution to problem X to solve some NP hard problem,
-
that means that solving X has to be at least as hard as the NP hard problem
-
making it therefore NP hard.
-
Now, there's something sort of irritatingly circular or turtles all the way downish about this.
-
We want to show that some problems in NP hard we got some problem,
-
we have to show that we can reduce some other NP hard problem to it.
-
We need that problem to be NP hard. How do we show that that problem is NP hard.
-
Well, we can just show that there're some other NP hard problems that we could reduce to it
-
and so on and so on and so on, and it doesn't really seem like we could ever get anywhere this way.
-
But the good news is that back in 1971, Stephen Cook gave essentially the original NP hard problem
-
and that is SAT, so SAT we know is NP hard.
-
And the way that he showed that is really ingenious, he actually showed that if you had
-
something that could solve SAT, you could use it to simulate in polynomial time,
-
essentially an NP computer--right.
-
A computer that makes these non-deterministic choices, and since that's the case,
-
anything that we could run on an NP computer, we can turn into a SAT problem
-
and therefore, SAT is as hard as anything in NP, so that's great.
-
Cook got us off the ground here by giving an NP hard problem.
-
Now we have something else to target.
-
We have some other way if we want to start that some problems are NP hard.
-
We can just reduce SAT to it and then we're done, but at this point now,
-
there's actually a huge number of problems that are known to be NP hard.
-
If you encounter a new problem, it may already be known to be NP hard or it may very well be
-
that some know NP hard problem can be reduced to it,
-
so you don't necessarily have to go all the way to SAT to do it.