YouTube

Got a YouTube account?

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

English subtitles

← 09-16 Does The Story End Here?

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. Congratulations. You have now learned some very fundamental concepts
  2. of computer science, and you understand the issue of P vs NP.
  3. We've also shown that the problems that Alice, Bob, and Carol
  4. were working on are among the hardest problems in NP.
  5. They are NP-complete; so nobody knows if
  6. there's a polynomial-time algorithm for those problems,
  7. and actually finding 1 would be a sensation.
  8. Now, the question, of course, is what does that mean for Alice, Bob, and Carol?
  9. Should they just give up?
  10. Should they ask their bosses to give them a new problem?
  11. Or should they make their bosses watch this Udacity course?
  12. In the next unit, we'll be looking at 2 things:
  13. The first 1 is how to recognize that a problem is NP-complete.
  14. And we'll then turn our attention to what to do when you encounter an NP-complete problem.
  15. Because, well, there will not only be good news, but as it turns out,
  16. there's still some options available.
  17. It is possible to poke loopholes into the laws of NP-completeness.
  18. So there's still hope for Alice, Bob and Carol. So see you next time.