
Title:
SAT is NPHard  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 computerright.

A computer that makes these nondeterministic 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.