YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← SAT is NP-Hard - Intro to Algorithms

Get Embed Code
3 Languages

Showing Revision 3 created 05/25/2016 by Udacity Robot.

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